记录编号	86391	评测结果	AAAAAAAAAA
题目名称	[NOIP 2008]传纸条	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2014-01-25 18:10:45	内存使用	0.38 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<queue>
#include<deque>
using namespace std;
const int SIZEN=5010,INF=0x7fffffff;
class EDGE{
public:
	int from,to,cap,flow,cost;
};
vector<EDGE> edges;
vector<int> c[SIZEN];//邻接表
int N;//范围是从0到N
void addedge(int from,int to,int cap,int cost){
	edges.push_back((EDGE){from,to,cap,0,cost});
	edges.push_back((EDGE){to,from,0,0,-cost});
	int tot=edges.size()-2;
	c[from].push_back(tot);
	c[to].push_back(tot+1);
}
int anscost=0;
bool SPFA(int S,int T){
	queue<int> Q;
	bool inq[SIZEN]={0};
	int f[SIZEN]={0};
	int father[SIZEN]={0};
	int i,x;
	for(i=0;i<=N;i++) f[i]=-INF;
	f[S]=0,inq[S]=true,Q.push(S);
	while(!Q.empty()){
		x=Q.front();inq[x]=false;Q.pop();
		for(i=0;i<c[x].size();i++){
			EDGE& e=edges[c[x][i]];
			if(e.cap<=e.flow) continue;
			if(f[x]+e.cost>f[e.to]){
				f[e.to]=f[x]+e.cost;
				father[e.to]=c[x][i];
				if(!inq[e.to]){
					inq[e.to]=true;
					Q.push(e.to);
				}
			}
		}
	}
	int minf=INF;
	x=T;
	while(x!=S){
		EDGE& e=edges[father[x]];
		minf=min(minf,e.cap-e.flow);
		x=e.from;
	}
	anscost+=minf*f[T];
	x=T;
	int now;
	while(x!=S){
		now=father[x];
		edges[now].flow+=minf;
		edges[now^1].flow-=minf;
		x=edges[now].from;
	}
	return true;
}
void MCMF(int S,int T){
	SPFA(S,T);
	SPFA(S,T);
	printf("%d\n",anscost);
}
//下标从0开始
int S,T;
const int SIZEW=51;
int H,W;//H行W列
int warm[SIZEW][SIZEW]={0};
int hash(int x,int y){
	return x*W+y;
}
void init(void){
	scanf("%d%d",&H,&W);
	S=hash(0,0)+W*H;
	T=hash(H-1,W-1);
	N=T+W*H;
	//左上角的"起点"是0,右下角的"终点"是N
	for(int i=0;i<H;i++) for(int j=0;j<W;j++) scanf("%d",&warm[i][j]);
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			if(hash(i,j)==0||hash(i,j)==T) continue;
			addedge(hash(i,j),hash(i,j)+W*H,1,warm[i][j]);
		}
	}
	//+W*H以后就是出点
	for(int i=0;i<H;i++) for(int j=0;j<W-1;j++) addedge(hash(i,j)+W*H,hash(i,j+1),INF,0);
	for(int i=0;i<H-1;i++) for(int j=0;j<W;j++) addedge(hash(i,j)+W*H,hash(i+1,j),INF,0);
}
int main(){
	freopen("message.in","r",stdin);
	freopen("message.out","w",stdout);
	init();
	MCMF(S,T);
	return 0;
}