[方格取数]【二分图最大点权独立集】【最小割】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1475
【算法分析】
就是求一个二分图的最大点权独立集。
首先我们对图黑白染色，然后白的放X部，黑的放Y部。
再次假设我们取到所有格子上的权。
然后我们尝试最小割的一般构造方法。
对于X部点，如果属于割中源的那一边。那么就当做取这个点。如果属于汇的那一边，则不取。
对于Y部点，如果属于割中源的那一边。那么就当做不取这个点。如果属于汇的那一边，则取。
于是对应地连边。
对于i∈X部，那么连边S->i，容量应当是Wi。
对于i∈Y部，那么连边i->T，容量应当是Wi。
那么相邻的格子连边容量为INF.
对于割，证明命题：如果两点相邻，那么他们不会同时取。
先假设他们同时取了。
对于X部点，被割在了源那一边。
对于Y部点，被割在了汇那一边。
那么：这两点之间那条边，就成了割边！
又由于它是容量为INF的。那么不可能成为割边。
于是反证得上面的命题成立。
最后本题用最小割完美解决。
【其它】1Y。
【CODE】
#include #include #include const int N=35;
const int INF=0x7FFFFFFF;
struct edge{int x,y,c;edge *next,*op;}g[205555],*ls[N*N],*cur[N*N],*fa[N*N];
int n,S,T,e,Flow,Sum;
int color[N][N],num[N*N],d[N*N];

int pos(int x,int y){
if (x<1 || x>n || y<1 || y>n) return -100000;
return (x-1)*n+y;
}

void addedge(int x,int y,int c){
if (x<0 || y<0) return;
g[++e].x=x; g[e].y=y; g[e].c=c; g[e].next=ls[x]; ls[x]=&g[e]; g[e].op=&g[e+1];
g[++e].x=y; g[e].y=x; g[e].c=0; g[e].next=ls[y]; ls[y]=&g[e]; g[e].op=&g[e-1];
}

void init(){
scanf("%d",&n);
S=0; T=n*n+1;
e=0; memset(ls,0,sizeof(ls));
Sum=0;
for (int i=1;i<=n;i++)
for (int w,j=1;j<=n;j++){
if (j==1) color[i][j]=1-color[i-1][j];
else color[i][j]=1-color[i][j-1];
scanf("%d",&w);
Sum+=w;
if (color[i][j]){
addedge(S,pos(i,j),w);
addedge(pos(i,j),pos(i-1,j),INF);
addedge(pos(i,j),pos(i+1,j),INF);
addedge(pos(i,j),pos(i,j-1),INF);
addedge(pos(i,j),pos(i,j+1),INF);
}
else addedge(pos(i,j),T,w);
}
}

void relabel(int p){
cur[p]=ls[p];
int mm=T;
for (edge *t=ls[p];t;t=t->next)
if (t->c && d[t->y] d[p]=mm+1;
}

void change(){
int nf=INF;
for (int i=T;i!=S;i=fa[i]->x)
if (fa[i]->c Flow+=nf;
for (int i=T;i!=S;i=fa[i]->x){
fa[i]->c-=nf;
fa[i]->op->c+=nf;
}
}

void sap(){
int i;
Flow=0;
for (i=S;i<=T;i++){
d[i]=num[i]=0;
cur[i]=ls[i];
}
i=S;
while (d[S]<=T){
edge *&t=cur[i];
for (;t;t=t->next)
if (t->c && d[t->y]+1==d[t->x]) break;
if (t){
fa[t->y]=t;
i=t->y;
if (i==T){
change();
i=S;
}
}else{
if (!–num[d[i]]) break;
relabel(i);
++num[d[i]];
if (i!=S) i=fa[i]->x;
}
}
}

int main(){
init();
sap();
printf("%dn",Sum-Flow);
}