记录编号	430976	评测结果	AAAAAAAAAA
题目名称	王者之剑	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	0.043 s
提交时间	2017-07-30 21:24:08	内存使用	11.85 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
struct edge{
	int e,n,w;
}a[2000001];
int pre[100001],tot;
inline void insert(int s,int e,int w){
	a[tot].e=e;
	a[tot].w=w;
	a[tot].n=pre[s];
	pre[s]=tot++;
}
int n,m;
int w[105][105],col[105][105];
inline void paint(){
	int now(1);
	for(int i=1;i<=n;i++){
		now^=1;
		for(int j=1;j<=m;j++){
			if(j&1)
				col[i][j]=now;
			else
				col[i][j]=now^1;
		}
	}
}
int S(0),T;
int ans(0),inf(0x7fffffff),sum(0);
inline void build(){
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(col[i][j])
				insert(S,(i-1)*m+j,w[i][j]),insert((i-1)*m+j,S,0);
			else
				insert((i-1)*m+j,T,w[i][j]),insert(T,(i-1)*m+j,0);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(col[i][j]){
				if(i!=1)
					insert((i-2)*m+j,(i-1)*m+j,0),insert((i-1)*m+j,(i-2)*m+j,inf);
				if(i!=n)
					insert(i*m+j,(i-1)*m+j,0),insert((i-1)*m+j,i*m+j,inf);
				if(j!=1)
					insert((i-1)*m+j-1,(i-1)*m+j,0),insert((i-1)*m+j,(i-1)*m+j-1,inf);
				if(j!=m)
					insert((i-1)*m+j+1,(i-1)*m+j,0),insert((i-1)*m+j,(i-1)*m+j+1,inf);
			}
		}
}
int dis[10010];
inline bool bfs(int s,int t){
	memset(dis,0,sizeof(dis));
	dis[s]=1;
	queue<int>q;
	q.push(s);
	while(!q.empty()){
		int k(q.front());
		q.pop();
		for(int i=pre[k];i!=-1;i=a[i].n){
			int e(a[i].e);
			if(!dis[e]&&a[i].w){
				dis[e]=dis[k]+1;
				q.push(e);
				if(e==t)
					return true;
			}
		}
	}
	return false;
}
inline int my_min(int a,int b){
	return a<b?a:b;
}
inline int dfs(int now,int flow){
	if(now==T)
		return flow;
	int tmp(flow),f;
	for(int i=pre[now];i!=-1;i=a[i].n){
		int e(a[i].e);
		if(dis[e]==dis[now]+1&&tmp&&a[i].w){
			f=dfs(e,my_min(tmp,a[i].w));
			if(!f){
				dis[e]=0;
				continue;
			}
			a[i].w-=f;
			a[i^1].w+=f;
			tmp-=f;
		}
	}
	return flow-tmp;
} 
inline int gg(){
	freopen("Excalibur.in","r",stdin);
	freopen("Excalibur.out","w",stdout);
	memset(pre,-1,sizeof(pre));
	n=read(),m=read();
	T=n*m+1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			w[i][j]=read(),sum+=w[i][j];
	paint();
	build();
	while(bfs(S,T))
		ans+=dfs(S,inf);
	printf("%d",sum-ans);
	return 0;
}
int K(gg());
int main(){;}