734. [网络流24题] 方格取数问题
★★☆ 输入文件：grid.in 输出文件：grid.out 简单对比时间限制：1 s 内存限制：128 MB
3 2 3
2 3 1
grid.out
11
(1<=N,M<=30)
根据奇偶性转为二分图后
选出的点满足任意两个都不相邻，这是点独立集的概念
使选出的总和最大:最大点权独立集
最大点权独立集=总点权-最小点权覆盖集=总点权-最小割=总点权-最大流
取得数总和最大转化为不取的损失最小
所以问题即可以转化为割掉最小的边，使原图不连通（即找不出方格中相邻且二分图中有边相连的点）
此二分图中只有两种边，源点向奇格的边，inf边，偶格向汇点的边
割掉最小的边一定不会割inf边
又因为源点向所有奇格有连边，汇点与所有偶格有连边
利用奇偶格做二分图可以使与同一格相连的所有格都不与这个格在同一集合内
所以若要使图不连通，必须割掉与同一奇格相连的所有边，或与同一偶格相连的所有边
所以最小损失相当于最小割
#include#include #include #define N 910#define M N*12#define inf 0x7fffffffusing namespace std;int n,m,ans,tot=1,sum,a[31][31];int src,decc,nextt[M],to[M],front[N],cap[M],lev[N],cur[N];queue q;void add(int u,int v,int w){ to[++tot]=v;nextt[tot]=front[u];front[u]=tot;cap[tot]=w; to[++tot]=u;nextt[tot]=front[v];front[v]=tot;cap[tot]=0;}bool bfs() { for(int i=0;i<=decc;i++) {cur[i]=front[i];lev[i]=-1;} while(!q.empty()) q.pop(); q.push(src);lev[src]=0; while(!q.empty()) { int now=q.front();q.pop(); for(int i=front[now];i!=0;i=nextt[i]) { int t=to[i]; if(cap[i]>0&&lev[t]==-1) { q.push(t); lev[t]=lev[now]+1; if(t==decc) return true; } } } return false; } int dinic(int now,int flow) { if(now==decc) return flow; int delta,rest=0; for(int & i=cur[now];i!=0;i=nextt[i]) { int t=to[i]; if(lev[t]==lev[now]+1&&cap[i]>0) { delta=dinic(t,min(cap[i],flow-rest)); if(delta) { cap[i]-=delta;cap[i^1]+=delta; rest+=delta;if(rest==flow) break; } } } if(rest!=flow) lev[now]=-1; return rest; } int main(){ freopen("grid.in","r",stdin); freopen("grid.out","w",stdout); scanf("%d%d",&n,&m); int x; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]),sum+=a[i][j]; decc=n*m+1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if((i+j)%2) { add(src,(i-1)*m+j,a[i][j]); if(j!=1) add((i-1)*m+j,(i-1)*m+j-1,inf); if(j!=m) add((i-1)*m+j,(i-1)*m+j+1,inf); if(i!=1) add((i-1)*m+j,(i-2)*m+j,inf); if(i!=n) add((i-1)*m+j,i*m+j,inf); } else add((i-1)*m+j,decc,a[i][j]); while(bfs()) ans+=dinic(src,inf); printf("%d",sum-ans);}