有一个 m 行 n列的方格图,每个方格中都有一个正整数。
现要从方格中取数,使任意两个数所在方格没有公共边,且取出的数的总和最大,请求出最大的和。
相邻格子连边,形成一个二分图, 现在要删去一些边( 边权和最小) ,使得S-T不连通,即最小割
SUM - 最小割
#include<iostream> #include<algorithm> #include<cstring> #include<queue> #define IOS std::ios::sync_with_stdio(0) using namespace std; const int N=1e4,M=5e5; #define inf 1e9 int n,m,B,W,a[N][N],id[102][102]; int all=1,hd[N],go[M],w[M],nxt[M]; int S,T; int dis[M],ans=0,now[M]; void add_(int x,int y,int z){ nxt[++all]=hd[x]; hd[x]=all; go[all]=y; w[all]=z; swap(x,y); nxt[++all]=hd[x]; hd[x]=all; go[all]=y; w[all]=0; } bool bfs(){ for(int i=0;i<M;i++)dis[i]=inf; queue<int> q; q.push(S); now[S]=hd[S]; dis[S]=0; while(q.empty()==0){ int x=q.front(); q.pop(); for(int i=hd[x];i;i=nxt[i]){ int y=go[i]; if(w[i]>0&&dis[y]==inf){ dis[y]=dis[x]+1; now[y]=hd[y]; q.push(y); if(y==T) return 1; } } } return 0; } int dfs(int x,int sum){ if(x==T) return sum; int k,res=0; for(int i=now[x];i&& sum ;i=nxt[i]){ now[x]=i; int y=go[i]; if(w[i]>0&&(dis[y]==dis[x]+1)){ k=dfs(y,min(sum,w[i])); if(k==0) dis[y]=inf; w[i]-=k; w[i^1]+=k; res+=k; sum-=k; } } return res; } int dx[4]={-1,1,0,0},dy[4]={0,0,1,-1} ,SUM=0,col[102][102]; int ID(int x,int y){ return (x-1)*m+y; } bool ok(int x,int y){ return x>0&&x<=n&&y>0&&y<=m; } void dinic(){ int ans =0; while(bfs()) ans+=dfs(S,inf); cout<<SUM-ans<<endl; } signed main(){ cin>>n>>m; int i,j; for(i=1;i<=n;i++) for(j=1;j<=m;j++) cin>>a[i][j],SUM+=a[i][j]; S=0,T=n*m+1; for(i=1;i<=n;i++) for(j=1;j<=m;j++){ id[i][j]= m*(i-1)+j; col[i][j]=(i+j)%2; } for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(col[i][j]){ add_(S,id[i][j],a[i][j]); for(int k=0;k<4;k++) { int xx=i+dx[k],yy=j+dy[k]; if(ok(xx,yy)) add_(id[i][j],id[xx][yy],inf); } } for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(col[i][j]==0){ add_(id[i][j],T,a[i][j]); } dinic(); }
标签:return,int,取数,方格,&&,go,P2774,hd,dis From: https://www.cnblogs.com/towboa/p/17274350.html