方格取数问题 问题描述： 在一个有m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任 意2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。 «编程任务： 对于给定的方格棋盘，按照取数要求编程找出总和最大的数。 «数据输入： 由文件grid.in提供输入数据。文件第1 行有2 个正整数m和n，分别表示棋盘的行数 和列数。接下来的m行，每行有n个正整数，表示棋盘方格中的数。 «结果输出: 程序运行结束时，将取数的最大总和输出到文件grid.out中。 输入文件示例 输出文件示例 grid.in 3 3 1 2 3 3 2 3 2 3 1 grid.out 11
(1<=N,M<=30) 这个题可以转换成二分图，因为每个点的临边都可以分到对面的集合。然后取出最大的数使其互不相连。是否想到了二分图的最大点独立数？不同的是这里得点有点权。那就是求最大点权独立数了。最大点独立数+最小点覆盖数=总点数，则类比一下最大点权独立数+最小点权覆盖数=总点权。而最小点覆盖数又等于最大匹配，所以求最大匹配即可，只是这里的匹配是带权匹配，在用总点权减掉最大匹配即可。同样可以用网络流跑一边。 代码
#include<iostream> #include<cstdio> #include<queue> #include<cstring> #define N 1000 #define M 10000 #define inf 0x7ffffff using namespace std; int m,n,ans,cntn,sum; queue<int>team; struct E{ int to,next,c; }a[M*2];int last[N],dis[N],cnt; void build(int u,int v,int c) { a[++cnt].to=v;a[cnt].next=last[u]; a[cnt].c=c;last[u]=cnt; a[++cnt].to=u;a[cnt].next=last[v]; a[cnt].c=0;last[v]=cnt; } bool bfs() { memset(dis,-1,sizeof(dis)); team.push(910);dis[910]=0; while(!team.empty()){ int x=team.front();team.pop(); for(int i=last[x];i;i=a[i].next){ if(a[i].c&&dis[a[i].to]==-1){ dis[a[i].to]=dis[x]+1; team.push(a[i].to); } } } return dis[920]>-1; } int dfs(int x,int f) { if(x==920)return f; int now=0,b; for(int i=last[x];i;i=a[i].next) if(a[i].c&&dis[a[i].to]==dis[x]+1){ b=dfs(a[i].to,min(f-now,a[i].c)); a[i].c-=b;a[i^1].c+=b;now+=b; if(now==f)break; } if(!now)dis[x]=-1; return now; } int main() { freopen("grid.in","r",stdin); freopen("grid.out","w",stdout); ans=0; cnt=1; scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { int x;scanf("%d",&x);sum+=x; if((i+j)%2==0){ build(910,++cntn,x); if(i>1)build(cntn,cntn-m,inf); if(i<n)build(cntn,cntn+m,inf); if(j>1)build(cntn,cntn-1,inf); if(j<m)build(cntn,cntn+1,inf); } else build(++cntn,920,x); } while(bfs()) ans+=dfs(910,0x7fffffff); printf("%d\n",sum-ans); return 0; }