记录编号	91985	评测结果	AAAAAAAAAA
题目名称	运输问题2	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2014-03-17 21:21:19	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int SIZEN=150,INF=0x7fffffff;
class EDGE{
public:
	int from,to,cap,flow;
};
vector<EDGE> edges;
int h[SIZEN]={0},e[SIZEN]={0};
queue<int> Q;
vector<int> c[SIZEN];
int S,T,N;//1到N
void addedge(int from,int to,int cap){
	edges.push_back((EDGE){from,to,cap,0});
	edges.push_back((EDGE){to,from,0,0});
	int tot=edges.size()-2;
	c[from].push_back(tot);
	c[to].push_back(tot+1);
}
void push(int x,int k){
	EDGE &now=edges[k];
	if(now.cap<=now.flow) return;
	int cf=min(now.cap-now.flow,e[x]);
	e[x]-=cf,e[now.to]+=cf,now.flow+=cf,edges[k^1].flow-=cf;
	if(now.to!=S&&now.to!=T&&e[now.to]) Q.push(now.to);
}
void singlenode(int x){
	while(e[x]){
		int nowmin=INF;
		for(int i=0;i<c[x].size();i++){
			EDGE &now=edges[c[x][i]];
			if(now.cap<=now.flow) continue;
			if(h[now.to]==h[x]-1){
				push(x,c[x][i]);
				if(!e[x]) return;
			}
			else nowmin=min(nowmin,h[now.to]);
		}
		h[x]=nowmin+1;
	}
}
void maxflow(int s,int t,int n){
	S=s,T=t,N=n;
	memset(h,0,sizeof(h)),memset(e,0,sizeof(e));
	h[S]=n,e[S]=INF;
	for(int i=0;i<c[S].size();i++) push(S,c[S][i]);
	while(!Q.empty()){
		int u=Q.front();Q.pop();
		singlenode(u);
	}
}
int n;
void work(void){
	EDGE &tsback=edges[edges.size()-2];
	maxflow(0,n+1,n+1);
	int ans=tsback.flow;
	edges[edges.size()-2].cap=edges[edges.size()-2].flow;
	edges[edges.size()-1].cap=edges[edges.size()-1].flow;//把s,t间的边设为无效
	maxflow(1,n,n);
	ans+=e[n];
	printf("%d\n",ans);
}
void init(void){
	scanf("%d",&n);
	int lb,ub;//下界和上界
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%d%d",&lb,&ub);
			if(ub){
				addedge(i,j,ub-lb);
				addedge(0,j,lb);
				addedge(i,n+1,lb);
			}
		}
	}
	addedge(n,1,INF);
}
int main(){
	freopen("maxflowb.in","r",stdin);
	freopen("maxflowb.out","w",stdout);
	init();
	work();
	return 0;
}