HDU-1565ネットワークストリーム最小割合

Problem Descriptionはnnの格子の碁盤をあげて、各格子の中に非負の数があります.任意の2つの数が存在する格子に共通のエッジがないように、いくつかの数を取り出します.つまり、取得した数が存在する2つの格子が隣接することができず、取得した数の和が最大になります.Inputは複数の試験例を含み、各試験例は1つの整数nとnn個の非負数(n<=20)Outputを含み、各試験例について、取得可能な最大値とSample Input 3 75 15 21 75 15 28,725 Sample Output 188の解題構想を出力する:Sから各奇数格子点まで1つの流量がその重み値である辺、各奇数格子点から隣接する偶数格子点まで1つの流量が無限大である辺、各偶数格子点からE連の1本の流量がその重み値の辺で、最小割を求めて、つまり最大流です;コード:

#include
using namespace std;
inline int read(){
    	int x=0,f=0;char ch=getchar();
    	while(ch>'9'||ch<'0')f|=ch=='-',ch=getchar();
    	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    	return f?-x:x;
}
namespace NetFlow{
	const int MAXN=1e3,MAXM=1e5,INF=0x3f3f3f3f;// / 
	struct Edge{
		int to,next,cap,flow;
	}edge[MAXM];
	int tol,head[MAXN],gap[MAXN],dep[MAXN],cur[MAXN],Q[MAXN],S[MAXN];
	void init(){tol=0;memset(head,-1,sizeof(head));}
	void link(int u,int v,int w){
		edge[tol]={v,head[u],w,0},head[u]=tol++;
		edge[tol]={u,head[v],0,0},head[v]=tol++;
	}
	void BFS(int start,int end){
		memset(dep,-1,sizeof(dep));
		memset(gap,0,sizeof(gap));
		gap[0]=1,dep[end]=0;
		int front=0,rear=0;
		Q[rear++]=end;
		while(front!=rear){
			int u=Q[front++];
			for(int i=head[u];i!=-1;i=edge[i].next){
				int v=edge[i].to;
				if(dep[v]!=-1)continue;
				Q[rear++]=v,dep[v]=dep[u]+1;
				++gap[dep[v]];
			}
		}
	}
	int ISAP(int start,int end,int N){// / / 
		BFS(start,end);
		memcpy(cur,head,sizeof(head));
		int top=0,u=start,maxflow=0;
		while(dep[start]<N){
			if(u==end){
				int Min=INF,inser;
				for(int i=0;i<top;++i)if(Min>edge[S[i]].cap-edge[S[i]].flow)
					Min=edge[S[i]].cap-edge[S[i]].flow,inser=i;
				for(int i=0;i<top;++i)edge[S[i]].flow+=Min,edge[S[i]^1].flow-=Min;
				maxflow+=Min,top=inser,u=edge[S[top]^1].to;
				continue;
			}
			bool flag=false;int v;
			for(int i=cur[u];i!=-1;i=edge[i].next){
				v=edge[i].to;
				if(edge[i].cap-edge[i].flow&&dep[v]+1==dep[u]){
					flag=true,cur[u]=i;break;
				}
			}if(flag){
				S[top++]=cur[u];
				u=v;continue;
			}
			int Min=N;
			for(int i=head[u];i!=-1;i=edge[i].next)
				if(edge[i].cap-edge[i].flow&&dep[edge[i].to]<Min)
					Min=dep[edge[i].to],cur[u]=i;
			--gap[dep[u]];
			if(!gap[dep[u]])return maxflow;
			dep[u]=Min+1;++gap[dep[u]];
			if(u!=start)u=edge[S[--top]^1].to;
		}
		return maxflow;
	}
}
using namespace NetFlow;
int f[4][2]={1,0,0,1,-1,0,0,-1},mp[21][21],n;
int main(){
	while(~scanf("%d",&n)){
		init();
		int sum=0;
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j){
				mp[i][j]=read();
				sum+=mp[i][j];
				if((i+j)&1)link(0,i*n+j-n,mp[i][j]);
				else link(i*n+j-n,n*n+1,mp[i][j]);
			}
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)if((i+j)&1)
				for(int k=0;k<4;++k){
					int x=i+f[k][0],y=j+f[k][1];
					if(x<1||y<1||x>n||y>n)continue;
					link(i*n+j-n,x*n+y-n,INF);
				}
		printf("%d
",sum-ISAP(0,n*n+1,n*n+1));
	}
	return 0;
}