1324: Exca王者之剑

Description

Input

Output

Sample Input

Sample Output

——分割线——

这道题是一个最小割的模型。

代码：

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

inline int remin(int a,int b){

	if (a<b) return a;

	return b;

}

const int inf=214748360;

const int Maxm=100000;

struct EdgeNode{

	int u;

	int v;

	int f;

	int nxt;

	EdgeNode(){}

	EdgeNode(int a,int b,int c,int d){

		u=a;

		v=b;

		f=c;

		nxt=d;

	}

};

int nume=1;

EdgeNode e[Maxm+5];

const int Maxn=10000;

int src,sink;

int g[Maxn+7];

inline void insertEdgeFunction(int u,int v,int f){

	e[++nume]=EdgeNode(u,v,f,g[u]);

	g[u]=nume;

}

inline void insert(int u,int v,int f){

	insertEdgeFunction(u,v,f);

	insertEdgeFunction(v,u,0);

}

queue<int> que;

int dist[Maxn+5];

inline bool Bfs(){

	while(!que.empty()) que.pop();

	memset(dist,-1,sizeof(dist));

	que.push(src);

	dist[src]=0;

	while(!que.empty()){

		int point=que.front();

		que.pop();

		for(int i=g[point];i;i=e[i].nxt){

			if (e[i].f!=0 && dist[e[i].v]==-1){

				que.push(e[i].v);

				dist[e[i].v]=dist[point]+1;

			}

		}

	}

	return dist[sink]!=-1;

}

int Dfs(int p,int delta){

	int ret=0;

	if (p==sink){

		return delta;

	}else{

		for (int i=g[p];i;i=e[i].nxt){

			if (dist[e[i].v]==dist[p]+1 && e[i].f!=0){

				int dret=Dfs(e[i].v,remin(e[i].f,delta));

				//printf("%d\n",dret);

				ret+=dret;

				e[i].f-=dret;

				e[i^1].f+=dret;

				delta-=dret;

			}

		}

	}

	return ret;

}

inline int Dinic(){

	int ret=0;

	while(Bfs()){

		ret+=Dfs(src,inf);

	}

	return ret;

}

int n,m;

int sum=0;

int map[105][105];

int hash[105][105];

int cnt=0;

int main(){

	scanf("%d%d",&n,&m);

	for (int i=1;i<=n;i++){

		for (int j=1;j<=m;j++){

			scanf("%d",&map[i][j]);

			sum+=map[i][j];

			hash[i][j]=++cnt;

		}

	}

	src=0;

	sink=cnt+1;

	for(int i=1;i<=n;i++){

		for (int j=1;j<=m;j++){

			if ((i+j+1)&1){

				insert(src,hash[i][j],map[i][j]);

			}else{

				insert(hash[i][j],sink,map[i][j]);

			}

			if ((i+j+1)&1){

				int dx[]={0,1,0,-1,0};

				int dy[]={0,0,1,0,-1};

				for (int k=1;k<=4;k++){

					int x=i+dx[k],y=j+dy[k];

					if (1<=x && x<=n && 1<=y && y<=m) insert(hash[i][j],hash[x][y],inf);

				}

			}

		}

	} 

	printf("%d\n",sum-Dinic());

	return 0;

}