记录编号	113400	评测结果	AAAAAAAAAA
题目名称	战争传说	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.396 s
提交时间	2014-07-22 09:00:49	内存使用	0.31 MiB

#include<fstream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<deque>
using namespace std;
const int INF=0x7FFFFFFF;
ifstream fi("war.in");
ofstream fo("war.out");

int N,M,S,T;
class EDGE
{
public:
	int u,v,c,f;
};
vector <EDGE> E;
vector <EDGE> save_E;
vector <int> p[110];
vector <int> save_p[110];
void Addedge(int a,int b,int c)
{
	E.push_back((EDGE){a,b,c,0});
	E.push_back((EDGE){b,a,0,0});
	int tot=E.size();
	p[a].push_back(tot-2);
	p[b].push_back(tot-1);
} 
deque <int> Q;
int d[110],cur[110];
bool build()
{
	int u,v;
	memset(d,-1,sizeof(d));
	Q.clear();
	Q.push_back(S);
	d[S]=0;
	while(!Q.empty())
	{
		u=Q.front();Q.pop_front();
		for(unsigned int i=0;i<p[u].size();i++)
		{
			v=E[p[u][i]].v;
			if(E[p[u][i]].c>E[p[u][i]].f && d[v]==-1)
			{
				d[v]=d[u]+1;
				//if(v==T)return true;
				Q.push_back(v);
			}
		}
	}
	if(d[T]>0)
		return true;
	return false;
}
int search(int x,int low)
{
	if(x==T||!low)return low;
	int ret=0,flow=0,temp,y;
	for(unsigned int i=cur[x];i<p[x].size();i++)
	{
		cur[x]=i;
		temp=p[x][i];y=E[temp].v;
		if(d[y]==d[x]+1)
		{
			if( ret = search(y,min(low,(E[temp].c-E[temp].f) ) ) )
			{
				E[temp].f+=ret;
				E[temp^1].f-=ret;
				flow+=ret;
				low-=ret;
				//return ret;
			}
			if(!low)break;
		}
	}
	if(!flow)
		d[x]=-1;
	return flow;
}
int DINIC()
{
	int maxflow=0;
	while(build())
	{
		memset(cur,0,sizeof(cur));
		maxflow+=search(S,INF);
	}
	return maxflow;
}
int main()
{
	int Tt,step1,step2,part1,part2;
	fi>>Tt;
	while(Tt--)
	{
		E.clear();
		for(int i=1;i<=N;i++)
			p[i].clear();
		//================================
		fi>>N>>M;
		int a,b,c;
		for(int i=1;i<=M;i++)
		{
			fi>>a>>b>>c;
			Addedge(a,b,c);
		}
		//================================
		S=1;T=N;
		step1=DINIC();
		save_E=E;
		for(int i=1;i<=N;i++)
			save_p[i]=p[i];
		//================================
		part1=0;part2=0;
		for(int i=2;i<=N-1;i++)
		{
			E=save_E;
			for(int j=1;j<=N;j++)
				p[j]=save_p[j];
			S=1;T=i;
			part1=max(part1,DINIC());
			S=i;T=N;
			part2=max(part2,DINIC());
		}
		step2=min(part1,part2);
		//================================
		fo<<step1+step2<<endl;
	}
	
	return 0;
}