本文共 2373 字，大约阅读时间需要 7 分钟。
在一个有m * n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。
第1 行有2 个正整数m和n，分别表示棋盘的行数和列数。
将取数的最大总和输出
3 3
11
将每个点和它相邻的点标记为不同的颜色，然后把白点和Ｓ相连，黑点和Ｔ相连，容量为这个点的权值。
然后把每个白点和它相邻的黑点相连，容量为ｉｎｆ。
然后问题就转化为求二分图最大点权独立集。
根据某个定理，答案就等于总权值减去最小割。
#include #include #include #include #include #include #include #include #include #include #include #include #include #define inf 1999999999using namespace std;struct data{ int nex,to,w;}e[12000];int head[1000],edge=-1;int f[32][32],a[32][32],id[32][32],lev[1000];void add(int from,int to,int w){ e[++edge].nex=head[from]; e[edge].to=to; e[edge].w=w; head[from]=edge;}inline bool bfs(int s,int t){ queue q; q.push(s); memset(lev,0,sizeof(lev)); lev[s]=1; while(!q.empty()){ int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=e[i].nex) if(e[i].w>0 && !lev[e[i].to]){ lev[e[i].to]=lev[u]+1; q.push(e[i].to); if(e[i].to==t) return 1; } } return 0;}int dfs(int s,int t,int k){ if(s==t) return k; int tag=0; for(int i=head[s];i!=-1;i=e[i].nex) if(e[i].w>0 && lev[e[i].to]==lev[s]+1){ int d=dfs(e[i].to,t,min(k-tag,e[i].w)); e[i].w-=d; e[i^1].w+=d; tag+=d; if(tag==k) return tag; } return tag;}int dinic(int s,int t){ int flow=0; while(bfs(s,t)) flow+=dfs(s,t,inf); return flow;}int main(){ freopen("!.in","r",stdin); freopen("!.out","w",stdout); memset(head,-1,sizeof(head)); int n,m;scanf("%d%d",&n,&m); int s=0,t=n*m+1,tot=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]),tot+=a[i][j]; f[1][1]=1; for(int i=2;i<=m;i++) f[1][i]=f[1][i-1]^1; for(int i=2;i<=n;i++) for(int j=1;j<=m;j++) f[i][j]=f[i-1][j]^1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) id[i][j]=(i-1)*m+j; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ int k=id[i][j]; if(f[i][j]){ add(s,k,a[i][j]),add(k,s,0); if(i-1>0) add(k,id[i-1][j],inf),add(id[i-1][j],k,0); if(i+1<=n) add(k,id[i+1][j],inf),add(id[i+1][j],k,0); if(j-1>0) add(k,id[i][j-1],inf),add(id[i][j-1],k,0); if(j+1<=m) add(k,id[i][j+1],inf),add(id[i][j+1],k,0); } else add(k,t,a[i][j]),add(t,k,0); } printf("%d",tot-dinic(s,t)); return 0;}
转载于:https://www.cnblogs.com/pantakill/p/6613464.html