记录编号	430867	评测结果	TTTTTTTTTT
题目名称	王者之剑	最终得分	0
用户昵称	天亮说晚安·	是否通过	未通过
代码语言	C++	运行时间	10.000 s
提交时间	2017-07-30 19:04:41	内存使用	4.33 MiB

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
# define inf 1061109567
#define maxn 100000
using namespace std;
 
int n,m,tot,baox[10005],baoy[10005];
int a[105][105],stand[105][105]; 
int se[10005],ans;
 
struct node{
	 int head[maxn],size;
	 int dep[maxn],S,T;
	 
	 struct node2{
	 	 int u,v,next,w;
	 }edge[maxn*2];
	 void add(int u,int v,int w){
	 	 edge[++size].v=v;
	 	 edge[size].u=u;
	 	 edge[size].w=w;
	 	 edge[size].next=head[u];
	 	 head[u]=size;
	 }
	 
	 bool Bfs(){
	     queue<int>cc;	
	 	 memset(dep,0,sizeof(dep));
	 	 dep[S]=1;cc.push(S);
	 	 while(!cc.empty()){
	 	      int r=cc.front();cc.pop();	 
	 	 	  for(int i=head[r];i;i=edge[i].next)
			      if(edge[i].w&&!dep[edge[i].v]){
			      	  dep[edge[i].v]=dep[r]+1;
			      	  cc.push(edge[i].v);
			      	  if(edge[i].v==T)  return true;
				  } 	
		 }
	 }
	 
	 int Dfs(int x,int cp){
	 	 if(x==T||cp==0)  return cp;
	 	 int sum=cp,q;
	 	 for(int i=head[x];i;i=edge[i].next)
	 	     if(edge[i].w&&dep[edge[i].v]==dep[x]+1&&sum){
			       q=Dfs(edge[i].v,min(sum,edge[i].w));      
			       if(q==0)  dep[edge[i].v]=0;
			       else{  
				       if(q&1){sum-=q;edge[i].w-=q;edge[i+1].w+=q;}
					   else   {sum-=q;edge[i].w-=q;edge[i-1].w+=q;}	    
				   }
			 }	
	 }
}YY;

 
void build(){
	 YY.S=0;YY.T=tot+1;
     for(int i=1;i<=tot;i++){ 
        int ji=0,ou=0;bool biao=0;
        if(baox[i]&1)ji++;else ou++;
        if(baoy[i]&1)ji++;else ou++;
        if(ji==2||ou==2)  biao=1;
        if(biao) 
		  {se[i]=1;YY.add(0,i,a[baox[i]][baoy[i]]);YY.add(i,0,0);}
		else 
		  {YY.add(i,YY.T,a[baox[i]][baoy[i]]);YY.add(YY.T,i,0);}
     }
     for(int i=1;i<=tot;i++){
         if(!se[i]) continue;
         int x=baox[i],y=baoy[i];
	     if(x-1>=1){YY.add(i,stand[x-1][y],inf);YY.add(stand[x-1][y],i,0);}
	     if(x+1<=n){YY.add(i,stand[x+1][y],inf);YY.add(stand[x+1][y],i,0);}
	     if(y-1>=1){YY.add(i,stand[x][y-1],inf);YY.add(stand[x][y-1],i,0);}
	     if(y+1<=m){YY.add(i,stand[x][y+1],inf);YY.add(stand[x][y+1],i,0);}
	 }
}
 
int main(){
freopen("Excalibur.in","r",stdin);
freopen("Excalibur.out","w",stdout);
     scanf("%d%d",&n,&m);
     for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
           scanf("%d",&a[i][j]);
           ans+=a[i][j];stand[i][j]=++tot;baox[tot]=i;baoy[tot]=j;
		}
     build();
     while(YY.Bfs())  ans-=YY.Dfs(YY.S,10000000);
	 cout<<ans<<endl;
//while(1);
}