记录编号	362449	评测结果	AAAAAAAAAA
题目名称	[NOIP 2008]传纸条	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2017-01-07 14:31:46	内存使用	11.95 MiB

#include <cmath>
#include <deque>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=55*55*2;
#define Inf 2e9
#define LL long long
#define ex(x) ( x%2==0 ? x-1 : x+1 ) 
struct Edge{
	int from,next,to,flow,cost;
}e[maxn*100];
int n,m,start,end,len,head[maxn];
int pos(int x,int y){
	return (x-1)*m+y;
}
void Insert(int x,int y,int flow,int cost){
	len++;
	e[len].from=x;e[len].to=y;
	e[len].flow=flow;e[len].cost=cost;
	e[len].next=head[x];
	head[x]=len;
}
void Add_edge(int x,int y,int flow,int cost){
	Insert(x,y,flow,cost);Insert(y,x,0,-cost);
}
int dis[maxn],flow[maxn],pre[maxn],nodis;
int ansflow,anscost;
bool f[maxn];
bool Max_Spfa(){
	memset(dis,-0x3f,sizeof(dis));dis[start]=0;
	memset(f,0,sizeof(f));f[start]=true;
	flow[start]=Inf;nodis=dis[end];
	deque<int> q;q.push_back(start);
	while(!q.empty()){
		int k=q.front();q.pop_front();
		f[k]=false;
		for(int i=head[k];i;i=e[i].next){
			int j=e[i].to;
			if(min(flow[k],e[i].flow)>0 && dis[j]<dis[k]+e[i].cost){
				dis[j]=dis[k]+e[i].cost;
				flow[j]=min(flow[k],e[i].flow);
				pre[j]=i;
				if(!f[j]){
					f[j]=true;
					if(!q.empty() && dis[q.front()]<dis[j])q.push_front(j);
					else q.push_back(j);
				}
			}
		}
	}
	if(dis[end]==nodis)return false;
	ansflow+=flow[end];
	anscost+=flow[end]*dis[end];
	int last=end;
	while(last!=start){
		e[pre[last]].flow-=flow[end];
		e[ex(pre[last])].flow+=flow[end];
		last=e[pre[last]].from;
	}
	return true;
}
void Maxcost_Maxflow(){
	while(Max_Spfa());
}
void Init();
int main(){
	freopen("message.in","r",stdin);freopen("message.out","w",stdout);
	Init();
	getchar();getchar();
	return 0;
}
void Init(){
	scanf("%d%d",&n,&m);
	start=1;end=pos(n,m)*2;//小技巧,不用特判来建立容量为Inf的边
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int valu;scanf("%d",&valu);
			Add_edge(pos(n,m)+pos(i,j),pos(i,j),1,valu);
			if(i<n)Add_edge(pos(i,j),pos(i+1,j)+pos(n,m),1,0);
			if(j<m)Add_edge(pos(i,j),pos(i,j+1)+pos(n,m),1,0);
		}
	}
	Maxcost_Maxflow();
	printf("%d\n",anscost);
}