记录编号	156709	评测结果	AAAAAAAAAA
题目名称	运输问题1	最终得分	100
用户昵称	wolf.	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2015-04-05 20:13:46	内存使用	0.32 MiB

#include<iostream>
#include<fstream>
#include<bitset>
#include<vector>
#include<deque>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdio>
using namespace std;
#if defined wolf
const string ok="OK";
const string kk="	";
ofstream nnew("maxflowa.in",ios::app);
ifstream fin("maxflowa.in");
#define fout cout
#define Endl endl
#else
ifstream fin("maxflowa.in");
ofstream fout("maxflowa.out");
#endif
class llink{
public:
	int from,to;
	int cap,flow;
	llink(){
	}
	llink(int a,int b,int c,int d){
		from=a;
		to=b;
		cap=c;
		flow=d;
	}
};
vector<llink> TT;//作为边的容器，需要通过G得到下标
vector<int> G[105];//G[x][y]是以x开始到y的边在TT中的下标 反向边用  TT[G[x][y]^1]表示
int work(const vector<int> path,int s,int t){//计算可增广路的相关信息
	int it=t,mmin=999999999;
	while(it!=s){//逆序寻找最小流
		llink& r=TT[path[it]];
		mmin=min(mmin,r.cap-r.flow);
		it=r.from;
	}
	it=t;
	while(it!=s){//逆序标记流的状态变化
		TT[path[it]].flow+=mmin;//正向流增加  最终小于等于cap
		TT[path[it]^1].flow-=mmin;//反向流减小一定小于0 因为其容量为0
		it=TT[path[it]].from;
	}
	return mmin;
}
int core(int n,int s,int t){
	int it=s,maxflow=0;
	vector<int> dis,num,path,care;
	//dis维护ISAP的核心算法 用于计算 dia[x]=dis[y]+1 x->y
	//num用于维护gap优化  num[x]表示现在处于x状态的dis有多少个
	//path用于维护回溯路径 path[x]表示点x回溯的路径在TT中的下标
	//care维护正在考虑的边 注意在fall后修改dis即retreat时要清零
	dis.resize(n+1,0);//初始化
	num=dis;path=dis;care=dis;
	num[0]=n;//必要的初始化
	while(dis[s]<n){//注意退出条件
		if(it==t){//找到可增广路
			maxflow+=work(path,s,t);
			it=s;//此时重置指针即可，不要重置care
		}
		bool fall=1;//标志
		for(int i=care[it];i<G[it].size();++i){//在剩下的边中找可行边，利用了care的优化
			llink& r=TT[G[it][i]];//为了避免非常长的下标索引
			if(r.cap>r.flow&&dis[it]==dis[r.to]+1){//满足可增广的两个条件
				fall=0;//即找到增广路
				care[it]=i;//更新care
				path[r.to]=G[it][i];//更新path
				it=r.to;//更新指针
				break;
			}
		}
		if(fall){//没有找到可行的通路
			int mmin=n-1;//找最大值
			for(int i=0;i!=G[it].size();++i){
				llink& r=TT[G[it][i]];
				if(r.cap>r.flow){//只在能连通的道路上找，如果正向边被闭塞则跳过
					mmin=min(mmin,dis[r.to]);//更新mmin
				}
			}
			num[dis[it]]--;//更新num
			if(num[dis[it]]==0){//实施gap优化
				break;
			}
			dis[it]=++mmin;//对dis的更新
			num[dis[it]]++;//对num即gap优化的更新
			care[it]=0;//对care的更新
			if(it!=s){//重要的条件
				it=TT[path[it]].from;//必要的回溯
			}
		}
	}
	return maxflow;//算法结束
}
int main(){
	int n;
	fin>>n;
	for(int i=1;i!=n+1;++i){
		for(int j=1;j!=n+1;++j){
			int a;
			fin>>a;
			if(a>0){
				G[i].push_back(TT.size());
				TT.push_back(llink(i,j,a,0));//添加正向边
				G[j].push_back(TT.size());
				TT.push_back(llink(j,i,0,0));//添加反向边
			}
		}
	}
	fout<<core(n,1,n);
	//-------------------------*/
	#if defined wolf
	cout<<endl<<(double)clock()/CLOCKS_PER_SEC<<'s'<<endl;
	#endif
	return 0;
}
//Designed by wolf
//Sun Apr 05 2015