记录编号	479337	评测结果	AAAAAAAAAA
题目名称	王者之剑	最终得分	100
用户昵称	rvalue	是否通过	通过
代码语言	C++	运行时间	0.106 s
提交时间	2017-12-18 16:57:54	内存使用	0.50 MiB

#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

const int MAXV=10010;
const int MAXN=110;
const int INF=0x3FFFFFFF;

struct Edge{
	int from;
	int to;
	int flow;
	Edge* rev;
	Edge* next;
};

Edge* top;
Edge* head[MAXV];

int m;
int n;
int sum;
int total;
int depth[MAXV];
int data[MAXN][MAXN];
bool color[MAXN][MAXN];
int number[MAXN][MAXN];

void Initialize();
bool BFS(int,int);
int Dinic(int,int);
int DFS(int,int,int);
int Convert(int,int);
void Insert(int,int,int);

int main(){
#ifndef ASC_LOCAL
	freopen("Excalibur.in","r",stdin);
	freopen("Excalibur.out","w",stdout);
#endif
	Initialize();
	printf("%d\n",sum-Dinic(0,m*n+1));
	return 0;
}

int Dinic(int s,int t){
	int ans=0;
	while(BFS(s,t)){
		ans+=DFS(s,INF,t);
	}
	return ans;
}

int DFS(int s,int flow,int t){
	if(s==t||flow==0)
		return flow;
	int tmp=flow;
	int k;
	for(Edge* i=head[s];i!=NULL&&tmp>0;i=i->next){
		if(i->flow!=0&&depth[i->to]==depth[s]+1){
			k=DFS(i->to,std::min(tmp,i->flow),t);
			if(k<=0)
				depth[i->to]=0;
			tmp-=k;
			i->flow-=k;
			i->rev->flow+=k;
		}
	}
	return flow-tmp;
}

bool BFS(int s,int t){
	memset(depth,0,sizeof(depth));
	std::queue<int> q;
	depth[s]=1;
	q.push(s);
	while(!q.empty()){
		s=q.front();
		q.pop();
		for(Edge* i=head[s];i!=NULL;i=i->next){
			if(depth[i->to]==0&&i->flow!=0){
				q.push(i->to);
				depth[i->to]=depth[s]+1;
				if(i->to==t)
					return true;
			}
		}
	}
	return false;
}

inline void Initialize(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			number[i][j]=++total;
			scanf("%d",&data[i][j]);
			sum+=data[i][j];
			if(i==1)
				color[i][j]=!color[i][j-1];
			else
				color[i][j]=!color[i-1][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(color[i][j]){
				Insert(0,Convert(i,j),data[i][j]);
				if(i>1)
					Insert(Convert(i,j),Convert(i-1,j),INF);
				if(i<n)
					Insert(Convert(i,j),Convert(i+1,j),INF);
				if(j>1)
					Insert(Convert(i,j),Convert(i,j-1),INF);
				if(j<m)
					Insert(Convert(i,j),Convert(i,j+1),INF);
			}
			else{
				Insert(Convert(i,j),n*m+1,data[i][j]);
			}
		}
	}
}

inline int Convert(int i,int j){
	return number[i][j];
}

inline void Insert(int a,int b,int flow){
	top=new Edge;
	Edge* tmp=top;
	top->from=a;
	top->to=b;
	top->flow=flow;
	top->next=head[a];
	head[a]=top;

	top=new Edge;
	tmp->rev=top;
	top->from=b;
	top->to=a;
	top->flow=0;
	top->next=head[b];
	head[b]=top;
	top->rev=tmp;
}