每日归档： 2019年1月28日

这是一道最小割转最大流的例题。
首先，我们发现，这一题要求我们求的是所取和。然后容易知道，所取和等于总和减去舍弃和。
故而，我们要使得所取和最大，就只需要使得舍弃和最小。
尝试用所取和来建图并且跑最大流，发现，它并不是那么容易地建成一个可靠的图。
正难则反，我们考虑怎么样才能让舍弃和最小。
于是尝试用舍弃和最小来建图并且跑最小割。观察题目的性质我们发现，所有的坐标和的奇偶性相同的方格，永远是互不影响的。
这启发我们建一个二分图。
我们不妨将奇点建在左侧，偶点建在右侧。然后从源点向奇点连容量为数值的边；从偶点向汇点连容量为数值的边。
于是，很显然，当我们割掉任何一条边的时候，就意味着相应的点是不取的。
接着我们将相邻的黑白点连容量为无穷大的边，这意味着这两个点之间至少有一个不能取。
然后跑最大流得到最小割即可。

#include<iostream>
#include<cstdio>
#include<queue>


const int INF=2147483647;
const int VERYBIG=0x3f3f3f3f; 

inline int Min(int A,int B){
	return A<B?A:B;
}


struct ee{
	int v;
	int w;
	int nxt;
}e[200005];
int h[40005],et=-1;
int dep[40005],nw[40005];

inline void Eadd(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}

inline void add(int U,int V,int W){
	Eadd(U,V,W);
	Eadd(V,U,0);
}

int n,m,s,t;

inline int calc(int X,int Y){
	return (X-1)*m+Y;
}

std::queue<int> q;
inline bool bfs(){
	for(int i=1;i<=t;++i){
		dep[i]=INF;
		nw[i]=h[i];
	}
	while(!q.empty()){
		q.pop();
	}
	dep[s]=0;
	q.push(s);
	int p;
	while(!q.empty()){
		p=q.front();
		q.pop();
		for(int i=h[p];i>=0;i=e[i].nxt){
			if(dep[e[i].v]==INF&&e[i].w){
				dep[e[i].v]=dep[p]+1;
				q.push(e[i].v);
			}
		}
	}
	return dep[t]<INF;
}

inline int dfs(int X,int V){
	if(!V||X==t){
		return V;
	}
	int cnt=0,val;
	for(int i=nw[X];i>=0;i=e[i].nxt){
		nw[X]=i;
		if(dep[e[i].v]==dep[X]+1){
			val=dfs(e[i].v,Min(e[i].w,V));
			if(val){
				V-=val;
				cnt+=val;
				e[i].w-=val;
				e[i^1].w+=val;
				if(!V){
					break;
				}
			}
			
		}
	}
	return cnt;
}

inline int dinic(){
	int ans=0;
	while(bfs()){
		ans+=dfs(s,INF);
	}
	return ans;
}

void init(){
	scanf("%d%d",&n,&m);
	s=n*m+1,t=n*m+2;
	for(int i=1;i<=t;++i){
		h[i]=-1;
	}
	int x,cnt=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&x);
			cnt+=x;
			if((i+j)&1){
				add(s,calc(i,j),x);
				if(i+1<=n){
					add(calc(i,j),calc(i+1,j),VERYBIG);
				}
				if(i-1>=1){
					add(calc(i,j),calc(i-1,j),VERYBIG);
				}
				if(j+1<=m){
					add(calc(i,j),calc(i,j+1),VERYBIG);
				}
				if(j-1>=1){
					add(calc(i,j),calc(i,j-1),VERYBIG);	
				}
			}else{
				add(calc(i,j),t,x);
			} 
		}
	}
	printf("%d\n",cnt-dinic());
}

int main(){
	init();
	return 0;
}