记录编号	125031	评测结果	AAAAAAAAAA
题目名称	[NOIP 2008]传纸条	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.093 s
提交时间	2014-10-07 12:51:56	内存使用	2.43 MiB

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cctype>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <ctime>
#define Vect deque<edge*>
#define pb push_back
#define iter(v) v::iterator
#define bg begin()
#define maxn (52)
#define maxv (5002)
using namespace std;

#if defined DEBUG
FILE *in = fopen("test","r");
#define out stdout
#else
FILE *in = fopen("message.in","r");
FILE *out = fopen("message.out","w");
#endif

inline void getint(int &k){
	char c = fgetc(in);
	while(!isdigit(c))c = fgetc(in);
	k = c - '0';
	while(isdigit(c = fgetc(in)))
		k = k * 10 + (c - '0');
}

struct edge{
	int w, vol, to;
	edge(){}
	edge(int W, int V, int T):w(W),vol(V),to(T){}
}E[maxv*6];
int preE[maxv];
int Ecnt = 0;
Vect adj[maxv];
int m, n, Vnum = 2, preV[maxv], ans = 0;
inline void addE(int &Ecnt, int f, int t, int w, int v){
	E[Ecnt] = edge(w,v,t);
	adj[f].pb(E + Ecnt++);
	E[Ecnt] = edge(-w,0,f);
	adj[t].pb(E + Ecnt++);
}

inline void init(){
	int i, j, w;
	getint(w);
	addE(Ecnt, 0, 1, w, 2);
	for(i = 1;i < n; ++i){
		getint(w);
		addE(Ecnt, Vnum-1, Vnum, 0, 1);
		addE(Ecnt, Vnum, Vnum+1, w, 1);
		Vnum += 2;
	}
	for(i = 1;i < m-1; ++i){
		getint(w);
		addE(Ecnt, Vnum-(n<<1)+1, Vnum, 0, 1);
		addE(Ecnt, Vnum, Vnum+1, w, 1);
		Vnum += 2;
		for(j = 1;j < n; ++j){
			getint(w);
			addE(Ecnt, Vnum-1, Vnum, 0, 1);
			addE(Ecnt, Vnum-(n<<1)+1, Vnum, 0, 1);
			addE(Ecnt, Vnum, Vnum+1, w, 1);
			Vnum += 2;
		}
	}
	getint(w);
	addE(Ecnt, Vnum-(n<<1)+1, Vnum, 0, 1);
	addE(Ecnt, Vnum, Vnum+1, w, 1);
	Vnum += 2;
	for(j = 1;j < n; ++j){
		getint(w);
		addE(Ecnt, Vnum-1, Vnum, 0, 1);
		addE(Ecnt, Vnum-(n<<1)+1, Vnum, 0, 1);
		if(j < n-1)addE(Ecnt, Vnum, Vnum+1, w, 1);
		else addE(Ecnt, Vnum, Vnum+1, 0, 2);
		Vnum += 2;
	}
}
bool spfa(int &d){
	int dis[maxv] = {0}, tmp, t;
	bool inq[maxv] = {0}, known[maxv] = {1};
	queue<int> Q;
	iter(Vect) it;
	inq[0] = 1, Q.push(0);
	while(!Q.empty()){
		tmp = Q.front(), Q.pop(), inq[tmp] = 0;
		it = adj[tmp].begin();
		for(;it != adj[tmp].end();++it){
			if((*it)->vol <= 0)continue;
			t = dis[tmp] + (*it)->w;
			if(t < 0)continue;
			if(!known[(*it)->to] || t > dis[(*it)->to]){
				dis[(*it)->to] = t;
				known[(*it)->to] = 1;
				preE[(*it)->to] = *it - E;
				preV[(*it)->to] = tmp;
				if(!inq[(*it)->to])inq[(*it)->to] = 1, Q.push((*it)->to);
			}
		}
	}
	d = dis[Vnum-1];
	if(known[Vnum-1])return 1;
	else return 0;
}
inline void aug(int &dis){
	int k = Vnum - 1;
	ans += dis;
	while(k != 0){
		E[preE[k]].vol -= 1;		
		E[preE[k]^1].vol += 1;
		k = preV[k];
	}
	dis = 0;
}
int main(){
	getint(m),getint(n);
	init();
	int dis = 0;
	while(spfa(dis))
		aug(dis);
	fprintf(out,"%d\n",ans);
	#if defined DEBUG
	cout << (double)clock() / CLOCKS_PER_SEC;
	#endif
	return 0;
}