题意
在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。
想法
我们将问题转化为：一开始所有格子都选，之后去掉价值和最少的一些格子使剩下的格子合法。 将方格黑白染色，白格子连向S，黑格子连向T，边权为这个格子的值（也就是说将格子转移到边上）。 相邻的黑白格子间连INF的边。（这样每条从S到T的路径都为 S->白格子->黑格子->T ， 这两个格子不能同时选，S->白格子 与 黑格子->T 间必然会割掉一条边） 注意一个小trick:对于永远不被割掉的边，边权设为INF 这样跑完最小割后，剩下的格子是合法的。而最小割的容量便为去掉的那些格子的价值和。
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#define INF 2000000000
using namespace std;
typedef long long ll;
const int N = 10005;
struct node{
int v,f;
node *next,*rev;
}pool[N*20],*h[N];
int cnt;
void addedge(int u,int v,int f){
node *p=&pool[++cnt],*q=&pool[++cnt];
p->v=v;p->next=h[u];h[u]=p; p->f=f;p->rev=q;
q->v=u;q->next=h[v];h[v]=q; q->f=0;q->rev=p;
}
int S,T;
int que[N],level[N];
bool bfs(){
int head=0,tail=0,u,v;
for(int i=S;i<=T;i++) level[i]=-1;
level[S]=1; que[tail++]=S;
while(head<tail){
u=que[head++];
for(node *p=h[u];p;p=p->next)
if(p->f && level[v=p->v]==-1){
level[v]=level[u]+1;
que[tail++]=v;
}
if(level[T]!=-1) return true;
}
return false;
}
int find(int u,int f){
int v,s=0,t;
if(u==T) return f;
for(node *p=h[u];p;p=p->next)
if(p->f && s<f && level[v=p->v]==level[u]+1){
t=find(v,min(f-s,p->f));
if(t){
s+=t;
p->f-=t;
p->rev->f+=t;
}
}
if(!s) level[u]=-1;
return s;
}
ll dinic(){
ll f=0;
while(bfs()) f+=find(S,INF);
return f;
}
int n,m;
int val[105][105];
bool check(int x,int y){
if(x<1 || y<1 || x>n || y>m) return false;
return true;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) scanf("%d",&val[i][j]);
ll sum=0;
S=0; T=n*m+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
sum=sum+val[i][j];
if((i+j)&1) addedge(S,(i-1)*m+j,val[i][j]);
else{
addedge((i-1)*m+j,T,val[i][j]);
continue;
}
for(int dx=-1;dx<2;dx++)
for(int dy=-1;dy<2;dy++)
if(dx*dy==0 && dx!=dy){
int t1=i+dx,t2=j+dy;
if(check(t1,t2)) addedge((i-1)*m+j,(t1-1)*m+t2,INF);
}
}
sum-=dinic();
printf("%lld\n",sum);
return 0;
}
转载于:https://www.cnblogs.com/lindalee/p/8719054.html
相关资源：数据结构—成绩单生成器
