2020-2021:teams:legal_string:王智彪:网络流入门
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:王智彪:网络流入门 [2021/07/14 16:46] 王智彪 |
2020-2021:teams:legal_string:王智彪:网络流入门 [2021/07/15 18:26] (当前版本) 王智彪 ↷ 页面2020-2021:teams:legal_string:网络流入门被移动至2020-2021:teams:legal_string:王智彪:网络流入门 |
||
|---|---|---|---|
| 行 723: | 行 723: | ||
| addedge(u,v,w); | addedge(u,v,w); | ||
| addedge(v,u,0); | addedge(v,u,0); | ||
| + | } | ||
| + | printf("%lld\n",sum-ISAP()); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | |||
| + | </hidden> | ||
| + | |||
| + | 7.[[https://www.luogu.com.cn/problem/P4313]] | ||
| + | |||
| + | 经典问题。大意：一个班坐成 $n×m$ 的矩阵，每个人选文科会获得一种满意值，选理科会获得另一种满意值，这个人和周围（上下左右）的人都选理科会额外获得第三种满意值，都选文科会额外获得第四种满意值，问如何让满意值最大。 | ||
| + | |||
| + | 仿照上一题，我们先将所有的满意值相加，再利用最小割减下去。对于一个点因为没有别的限制，所以不需要拆点，对于文科需要将源点连到这个点，理科是这个点连到汇点。 | ||
| + | |||
| + | 后两种额外的需要自己和周围的人都选同一科，是且的关系。并且由于我们建图的意义是割掉哪条边代表排除哪条边代表的那种情况，只有把这个奖励单独作为一个点，并且如果是文科，从源点连到这个点，权值为奖励值，奖励点分别和那几个座位代表的点相连，权值为 $inf$ ，才能使得如果有一个点不连源点则一定连了汇点，那么会有流从源点到奖励点再到那个点最后到汇点，只能将这个奖励的流割掉，所以满足题意。 | ||
| + | |||
| + | <hidden 代码> | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | int dx[5]={0,1,-1,0,0}; | ||
| + | int dy[5]={0,0,0,1,-1}; | ||
| + | |||
| + | bool check(int x,int y){ | ||
| + | return x>=1&&x<=n&&y>=1&&y<=m; | ||
| + | } | ||
| + | |||
| + | int main() { | ||
| + | while(~scanf("%d %d",&n,&m)) { | ||
| + | cnt=1; | ||
| + | memset(head,0,sizeof(head)); | ||
| + | s=n*m*4+1,t=n*m*4+2; | ||
| + | ll sum=0; | ||
| + | for(int i=1,tmp; i<=n; i++) { | ||
| + | for(int j=1; j<=m; j++) { | ||
| + | tmp=Read(); | ||
| + | sum+=tmp; | ||
| + | addedge(s,(i-1)*m+j,tmp); | ||
| + | addedge((i-1)*m+j,s,0); | ||
| + | } | ||
| + | } | ||
| + | for(int i=1,tmp; i<=n; i++) { | ||
| + | for(int j=1; j<=m; j++) { | ||
| + | tmp=Read(); | ||
| + | sum+=tmp; | ||
| + | addedge((i-1)*m+j,t,tmp); | ||
| + | addedge(t,(i-1)*m+j,0); | ||
| + | } | ||
| + | } | ||
| + | for(int i=1,tmp; i<=n; i++) { | ||
| + | for(int j=1; j<=m; j++) { | ||
| + | tmp=Read(); | ||
| + | sum+=tmp; | ||
| + | addedge(s,(i-1+n)*m+j,tmp); | ||
| + | addedge((i-1+n)*m+j,s,0); | ||
| + | for(int k=0;k<5;k++){ | ||
| + | int xx=i+dx[k],yy=j+dy[k]; | ||
| + | if(check(xx,yy)){ | ||
| + | addedge((i-1+n)*m+j,(xx-1)*m+yy,inf); | ||
| + | addedge((xx-1)*m+yy,(i-1+n)*m+j,0); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | for(int i=1,tmp; i<=n; i++) { | ||
| + | for(int j=1; j<=m; j++) { | ||
| + | tmp=Read(); | ||
| + | sum+=tmp; | ||
| + | addedge((i-1+2*n)*m+j,t,tmp); | ||
| + | addedge(t,(i-1+2*n)*m+j,0); | ||
| + | for(int k=0;k<5;k++){ | ||
| + | int xx=i+dx[k],yy=j+dy[k]; | ||
| + | if(check(xx,yy)){ | ||
| + | addedge((xx-1)*m+yy,(i-1+2*n)*m+j,inf); | ||
| + | addedge((i-1+2*n)*m+j,(xx-1)*m+yy,0); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| } | } | ||
| printf("%lld\n",sum-ISAP()); | printf("%lld\n",sum-ISAP()); | ||
2020-2021/teams/legal_string/王智彪/网络流入门.1626252403.txt.gz · 最后更改: 2021/07/14 16:46 由 王智彪
