记录编号	318985	评测结果	AAAAAAAAAA
题目名称	[NOIP 2008]传纸条	最终得分	100
用户昵称	Hzoi_	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2016-10-10 07:58:43	内存使用	76.66 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define INF ((~((1)<<(31)))>>(2))
using namespace std;
const int maxn=5010;
struct edge{int to,cap,cost,prev;}e[5000010];
void addedge(int,int,int,int);
void insert(int,int,int,int);
void maxcostflow();
void SPFA();
int dfs(int);
int n=0,m,c,id[60][60],last[maxn],len=0,ans=0,d[maxn],s,t,tmp;
bool inq[maxn],vis[maxn];
int main(){
#define MINE
#ifdef MINE
	freopen("message.in","r",stdin);
	freopen("message.out","w",stdout);
#endif
	memset(last,-1,sizeof(last));
	scanf("%d%d",&m,&c);
	for(int i=1;i<=m;i++)for(int j=1;j<=c;j++)id[i][j]=++n;
	for(int i=1;i<=m;i++)for(int j=1;j<=c;j++){
		scanf("%d",&tmp);
		addedge(id[i][j],id[i][j]+n,1,tmp);
		if(i>1)addedge(id[i-1][j]+n,id[i][j],INF,0);
		if(j>1)addedge(id[i][j-1]+n,id[i][j],INF,0);
	}
	addedge(id[1][1],id[1][1]+n,1,0);
	addedge(id[m][c],id[m][c]+n,1,0);
	s=id[1][1];
	t=id[m][c]+n;
	n=t;
	maxcostflow();
	printf("%d",ans);
#ifndef MINE
	printf("\n--------------------DONE--------------------\n");
	for(;;);
#endif
	return 0;
}
void addedge(int x,int y,int z,int w){
	insert(x,y,z,w);
	insert(y,x,0,-w);
}
void insert(int x,int y,int z,int w){
	e[len].to=y;
	e[len].cap=z;
	e[len].cost=w;
	e[len].prev=last[x];
	last[x]=len++;
}
void maxcostflow(){
	SPFA();
	memset(vis,0,sizeof(vis));
	dfs(s);
	SPFA();
	memset(vis,0,sizeof(vis));
	dfs(s);
}
void SPFA(){
	int x;
	queue<int>q;
	memset(inq,0,sizeof(inq));
	q.push(s);
	inq[s]=true;
	fill_n(d+1,n,-INF);
	d[s]=0;
	while(!q.empty()){
		x=q.front();
		q.pop();
		inq[x]=false;
		for(int i=last[x];i!=-1;i=e[i].prev)if(e[i].cap>0&&d[e[i].to]<d[x]+e[i].cost){
			d[e[i].to]=d[x]+e[i].cost;
			if(!inq[e[i].to]){
				q.push(e[i].to);
				inq[e[i].to]=true;
			}
		}
	}
}
int dfs(int x){
	if(vis[x])return 0;
	vis[x]=true;
	if(x==t)return 1;
	for(int i=last[x];i!=-1;i=e[i].prev)if(e[i].cap>0&&d[e[i].to]==d[x]+e[i].cost&&dfs(e[i].to)){
		ans+=e[i].cost;
		e[i].cap--;
		e[i^1].cap++;
		return 1;
	}
	return 0;
}