记录编号	430418	评测结果	AAAAAAAAAA
题目名称	王者之剑	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	0.042 s
提交时间	2017-07-29 19:12:06	内存使用	3.01 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
#include<iostream>
#include<cstring>
using namespace std;
#define LL long long
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define N 100000
const int inf=0x7fffffff;
struct haha{
	int next,to,w;
}edge[N];
int head[N],cnt;
int n,m,ji;
int s=0,t;
inline void add(int u,int v,int w){
	edge[cnt].w=w;
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}
int dep[N],ans;
int num[500][500],flag[500][500];
inline bool bfs(){
	memset(dep,0,sizeof(dep));
	queue<int> q;
	q.push(s);
	dep[s]=1;
	while(!q.empty()){
		int now=q.front();q.pop();
		for(int i=head[now];i!=-1;i=edge[i].next){
			int to=edge[i].to,w=edge[i].w;
			if(w&&(!dep[to])){
				dep[to]=dep[now]+1;
				q.push(to);
				if(to==t){
					return 1;
				}
			}
		}
	}
	return 0;
}
inline int dfs(int now,int f){
	if(now==t){
		return f;
	}
	int tmp=f;
	for(int i=head[now];i!=-1;i=edge[i].next){
		int to=edge[i].to,w=edge[i].w;
		if(w&&tmp&&dep[to]==dep[now]+1){
			int k=dfs(to,min(w,tmp));
			if(!k){
				dep[to]=0;
				continue;
			}
			edge[i].w-=k;
			edge[i^1].w+=k;
			tmp-=k;
		}
	}
	return f-tmp;
}
int tot;
int read()
{
    int su=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
       ch=getchar();
    while(ch<='9'&&ch>='0')
    {
        su=su*10+ch-'0';
        ch=getchar();
    }
          
    return su;
}
inline int haha(){
	freopen("Excalibur.in","r",stdin);
	freopen("Excalibur.out","w",stdout);
	n=read();m=read();
	t=n*m+1;
	memset(head,-1,sizeof(head));
	pos(i,1,n){
		if(i%2==0){
			flag[i][0]=1;
		}
	}
	int count[500][500]={0};
	pos(i,1,n){
		pos(j,1,m){
			num[i][j]=read();
			tot+=num[i][j];
			ji++;
			flag[i][j]=flag[i][j-1]^1;
			count[i][j]=ji;
		}
	}
	pos(i,1,n){
		pos(j,1,m){
			if(!flag[i][j]){
				add(s,count[i][j],num[i][j]);
				add(count[i][j],s,0);
			}
			else{
				add(count[i][j],t,num[i][j]);
				add(t,count[i][j],0);
			}
		}
	}
	pos(i,1,n){
		pos(j,1,m){
		  if(flag[i][j]==0){
		  	if(j>1){
				add(count[i][j],count[i][j-1],inf);
				add(count[i][j-1],count[i][j],0);
			}
			if(i>1){
				add(count[i][j],count[i-1][j],inf);
				add(count[i-1][j],count[i][j],0);
			}
			if(j<m){
				add(count[i][j],count[i][j+1],inf);
				add(count[i][j+1],count[i][j],0);
			}
			if(i<n){
				add(count[i][j],count[i+1][j],inf);
				add(count[i+1][j],count[i][j],0);
			}
		  }
		}
	}
	while(bfs()){
		ans+=dfs(s,inf);
	}
	cout<<tot-ans;
	return 0;
}
int sb=haha();
int main(){
	;
}