m*n 个方格，从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。
∑所有的数-min（相邻的取）
min（相邻的取）为最小割
//最小割 //longlong 写成int RE #include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; int m,n,cnt=1,hd[1005],vis[1005],d[1005]; long long a[1005][1005],sum; struct Edge{ int to,nxt,flw; }edge[100005<<1]; queue<int> q; void add(int u,int v,int w) { cnt++; edge[cnt].to=v; edge[cnt].nxt=hd[u]; edge[cnt].flw=w; hd[u]=cnt;//又少了这一句。。。 } int tot=0; int bfs(int s,int t) { memset(vis,0,sizeof vis); while(!q.empty()) q.pop(); vis[s]=1; d[s]=1; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=hd[u];i;i=edge[i].nxt) { int v=edge[i].to; if(edge[i].flw >0 && !vis[v]) { d[v]=d[u]+1; vis[v]=1; // cout<<u<<","<<v<<","<<d[v]<<","<<edge[i].flw<<endl; q.push(v); if(v==t) { return 1; } } } } return 0; } int s=0,t;//t=m*n+1,所以这里是0 int dinic(int u,int res) { if(u==t)return res; int sum=0; for(int i=hd[u];i;i=edge[i].nxt) { int v=edge[i].to ; if(edge[i].flw>0 && res>0 && d[v]==d[u]+1)//还有啥来着？ 分层。。。 { // cout<<u<<","<<v<<","<<min(res,edge[i].flw)<<endl; int k=dinic(v,min(res,edge[i].flw)); // if(!k) d[v]=0; edge[i].flw-=k; edge[i^1].flw+=k; sum+=k; res-=k; if(!res) break; } } return sum; } int main() { scanf("%d%d",&m,&n);//注意m是行n是列 t=n*m+1; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) { scanf("%d",&a[i][j]); sum+=a[i][j]; } for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) { int p=(i-1)*n+j; if((i+j)%2==1) //这是右部点(2,4,6,8...),为了左部点连接到右部点的边权是无穷大 { add((i-1)*n+j,t,a[i][j]); add(t,(i-1)*n+j,0); continue; //****continue右部点只和汇点连接，不和左部点连inf了 } add(s,(i-1)*n+j,a[i][j]); add((i-1)*n+j,s,0); if(i-1>0)//和它的上一行连边 { add(p,(i-2)*n+j,inf); add((i-2)*n+j,p,0); } if(j-1>0) { add(p,p-1,inf); add(p-1,p,0); } if(i+1<=m) { add(p,i*n+j,inf); add(i*n+j,p,0); } if(j+1<=n) { add(p,p+1,inf); add(p+1,p,0); } } // for(int u=0;u<=t;u++) // { // for(int i=hd[u];i;i=edge[i].nxt) // { // cout<<u<<","<<edge[i].to<<","<<edge[i].flw<<endl; // } // } // for(int i=s;i<=t;i++) // cout<<i<<":"<<d[i]<<","; long long mxflw=0; while(bfs(s,t)) { // for(int i=s;i<=t;i++) // cout<<i<<":"<<d[i]<<","; mxflw+=dinic(s,inf); } printf("%lld\n",sum-mxflw); }
转载于:https://www.cnblogs.com/caterpillor/p/9298400.html
相关资源：各显卡算力对照表！