记录编号	431173	评测结果	AAAAAAAAAA
题目名称	王者之剑	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	0.113 s
提交时间	2017-07-31 11:44:51	内存使用	2.01 MiB

#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>
#define inf 0x7fffffff
using namespace std;
int n,m,s,t,map[105][105],id[105][105],zz1,zz,st[80000],tot,ori,dis[80000];
bool cas[105][105],flag[80000];
struct node{
	   int to,next,flow;
}e[80000];
void add(int x,int y,int f){
	 e[zz].to=y;
	 e[zz].flow=f;
	 e[zz].next=st[x];
	 st[x]=zz; 
	 zz++;
}
bool bfs(){
	 queue<int> q;
	 memset(dis,-1,sizeof(dis));
	 q.push(s);
	 dis[s]=0;
	 while(!q.empty()){
	 	   int k=q.front();
	 	   q.pop();
	 	   for(int i=st[k];i!=-1;i=e[i].next){
	 	       int v=e[i].to;
			   if(dis[v]==-1&&e[i].flow){
			   	  dis[v]=dis[k]+1;
			   	  q.push(v);
			   }
		   }
	 }
	 if(dis[t]!=-1) return true;
	 else return false;
}
int dfs(int x,int last){
	if(x==t||last==0) return last;
	int ans=last;
	for(int i=st[x];i!=-1;i=e[i].next){
		int v=e[i].to;
		if(e[i].flow&&dis[v]==dis[x]+1&&ans!=0){
		   int tmp=dfs(v,min(e[i].flow,ans));
		   if(!tmp){
		   	  dis[v]=0;
		   	  continue;
		   }
		   e[i].flow-=tmp;
		   e[i^1].flow+=tmp;
		   ans-=tmp;
		}
	}return last-ans;
}
int main(){
    freopen("Excalibur.in","r",stdin);
    freopen("Excalibur.out","w",stdout);
	scanf("%d%d",&n,&m);
	memset(st,-1,sizeof(st));
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=m;j++){
	        scanf("%d",&map[i][j]);
			if((i+j)&1) cas[i][j]=true;
	        else cas[i][j]=false;
	        id[i][j]=++zz1;
			ori+=map[i][j];
	    }
	s=0,t=zz1+1;  
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=m;j++){
	        if(cas[i][j]){
	           add(id[i][j],t,map[i][j]);
	           add(t,id[i][j],0);
            }
            if(!cas[i][j]){
			   add(s,id[i][j],map[i][j]);
			   add(id[i][j],s,0);
			   if(i-1!=0) {add(id[i][j],id[i-1][j],inf);  add(id[i-1][j],id[i][j],0);}
			   if(i+1!=n+1) {add(id[i][j],id[i+1][j],inf);  add(id[i+1][j],id[i][j],0);}
			   if(j-1!=0) {add(id[i][j],id[i][j-1],inf);  add(id[i][j-1],id[i][j],0);}
			   if(j+1!=m+1) {add(id[i][j],id[i][j+1],inf);  add(id[i][j+1],id[i][j],0);} 
			}
        }
    while(bfs())tot+=dfs(s,0x7fffffff);
    printf("%d",ori-tot);
}