记录编号	52080	评测结果	AAAAAAAAAA
题目名称	运输问题1	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	0.046 s
提交时间	2013-01-12 15:04:35	内存使用	5.48 MiB

#include <fstream>
using namespace std;
ifstream fin("maxflowa.in");
ofstream fout("maxflowa.out");
int N,h[1000],e[1000],Map[1000][1000],r[1000][1000];
bool Inqueue[10000];
class Queue
{
public:
	int head,tail,list[10000];
}Q;
void Initialize()
{
int i,j;
	fin>>N;
	for(i=1;i<=N;i++)
		for(j=1;j<=N;j++)
		{
			fin>>Map[i][j];
			r[i][j]=Map[i][j];
		}
}

void PfR()
{
int i;
	h[1]=N;h[N]=0;Q.head=1;Q.tail=1;
	for(i=2;i<=N;i++)
		if(Map[1][i])
		{
			e[i]+=Map[1][i];
			r[1][i]-=Map[1][i];
			e[1]-=Map[1][i];
			r[i][1]+=Map[1][i];
			if(i!=N)
			{
				Q.list[Q.tail++]=i;
				Inqueue[i]=true;
			}
		}
	while(Q.head<Q.tail)
	{
	bool flag=false;
		for(i=1;i<=N;i++)
			if(r[Q.list[Q.head]][i] && h[Q.list[Q.head]]==h[i]+1)
			{
			int X=min(e[Q.list[Q.head]],r[Q.list[Q.head]][i]);
				r[Q.list[Q.head]][i]-=X;
				r[i][Q.list[Q.head]]+=X;
				e[Q.list[Q.head]]-=X;
				e[i]+=X;
				flag=true;
				if(!Inqueue[i] && i!=N)
				{
					Inqueue[i]=true;
					Q.list[Q.tail++]=i;
				}
				if(!e[Q.list[Q.head]])
					break;
			}
		if(e[Q.list[Q.head]]>0)
		{
		int Min=100000000;
			for(i=1;i<=N;i++)
				if(r[Q.list[Q.head]][i])
					Min=min(Min,h[i]);
			h[Q.list[Q.head]]=Min+1;
			Q.head--;
		}
		Inqueue[Q.list[Q.head]]=false;
		Q.head++;
	}
	fout<<e[N]<<endl;
}

int main()
{
	Initialize();
	
	PfR();
	
	fin.close();
	fout.close();
	return 0;
}