记录编号	58067	评测结果	WWWWTTTWTT
题目名称	战争传说	最终得分	0
用户昵称	QhelDIV	是否通过	未通过
代码语言	C++	运行时间	5.011 s
提交时间	2013-04-16 22:37:34	内存使用	3.97 MiB

#include <fstream>
#include <cstring>
#define F_I "war.in"
#define F_O "war.out"
using namespace std;
ifstream fin(F_I);
ofstream fout(F_O);
typedef long long ll;
const ll Inf=1234567890;
const ll Nx=201;
ll V,E,Map[Nx][Nx],Cf[Nx][Nx];
ll h[Nx],e[Nx],D,Max;
bool Inqueue[Nx];
class Queue
{
public:
	ll head,tail,list[10000];
}Q;
void push_relabel(ll s,ll t)
{
ll i;
	memset(e,0,sizeof(e));
	memset(h,0,sizeof(h));
	h[1]=V;h[V]=0;Q.head=1;Q.tail=1;
//	Inqueue[1]=true;
	for(i=2;i<=V;i++)
		if(Map[1][i])
		{
			e[i]+=Map[1][i];
			Cf[1][i]-=Map[1][i];
			e[1]-=Map[1][i];
			Cf[i][1]+=Map[1][i];
			if(i!=V)
			{
				Q.list[Q.tail++]=i;
				Inqueue[i]=true;
			}
		}
	while(Q.head<Q.tail)
	{
	bool flag=false;
		for(i=1;i<=V;i++)
			if(Cf[Q.list[Q.head]][i] && h[Q.list[Q.head]]==h[i]+1)
			{
			ll X=min(e[Q.list[Q.head]],Cf[Q.list[Q.head]][i]);
				Cf[Q.list[Q.head]][i]-=X;
				Cf[i][Q.list[Q.head]]+=X;
				e[Q.list[Q.head]]-=X;
				e[i]+=X;
				flag=true;
				if(!Inqueue[i] && i!=V && i!=1)
				{
					Inqueue[i]=true;
					Q.list[Q.tail++]=i;
				}
				if(!e[Q.list[Q.head]])
					break;
			}
		if(e[Q.list[Q.head]]>0)
		{
		ll Min=100000000;
			for(i=1;i<=V;i++)
				if(Cf[Q.list[Q.head]][i])
					Min=min(Min,h[i]);
			h[Q.list[Q.head]]=Min+1;
		}
		else{
			Inqueue[Q.list[Q.head]]=false;
			Q.head++;
		}
	}
	Max=max(Max,e[V]);
}

int main(){
ll i,j,a,b,c;
	fin>>D;
	while(D--){
		fin>>V>>E;
		Max=0;
		memset(Map,0,sizeof(Map));
		for(i=1;i<=E;i++){
			fin>>a>>b>>c;
			Map[a][b]=c;
			Cf[a][b]=c;
		}
		if(D!=0)
			continue;
		else
			int a;
		for(i=2;i<V;i++)
			for(j=2;j<V;j++)
				if(i!=j){
				ll temp=Map[i][j];
					Map[i][j]=Inf;
					for(ll z=1;z<=V;z++)
						for(ll x=1;x<=V;x++)
							Cf[z][x]=Map[z][x];
					push_relabel(1,V);
					Map[i][j]=temp;
			}
		if(Max==Inf)
			fout<<0<<endl;
		else
			fout<<Max<<endl;
	}
	fin.close();
	fout.close();
	return 0;
}