HDU4240_Route Redundancy

题目很简单、给一个有向图，求两点间的最大流量与任意一条路中的最大流量的比值。

最大流不说了，求出单条流量最大的路径可以用类似Spfa的方法来搞，保存到达当前点的最大流量，一直往下更新即可。

召唤代码君：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#define maxn 1010

#define Inf ~0U>>1

using namespace std;

vector<int> v[maxn];

int c[maxn][maxn],tag[maxn],d[maxn],a[maxn][maxn],f[maxn];

int n,m,s,t,ans,cap,cas,D,U,V,W;

int Q[maxn],bot,top;

bool can[maxn];

void _init()

{

	ans=cap=0;

	for (int i=1; i<=n; i++)

	{

		v[i].clear();

		for (int j=1; j<=n; j++) c[i][j]=a[i][j]=0;

	}

}

void bfs()

{

	for (int i=1; i<=n; i++) d[i]=9999,can[i]=false;

	Q[bot=top=1]=t,d[t]=0;

	while (bot<=top)

	{

		int cur=Q[bot++];

		for (unsigned i=0; i<v[cur].size(); i++)

		{

			if (c[v[cur][i]][cur]<=0 || d[cur]+1>=d[v[cur][i]]) continue;

			d[v[cur][i]]=d[cur]+1,Q[++top]=v[cur][i];

		}

	}

}

int dfs(int cur,int num)

{

	if (cur==t)

	{

		cap=max(cap,num);

		return num;

	}

	int k,tmp=num;

	for (unsigned i=0; i<v[cur].size(); i++)

	{

		if (c[cur][v[cur][i]]<=0 || can[v[cur][i]] || d[cur]!=d[v[cur][i]]+1)

			continue;

		k=dfs(v[cur][i],min(num,c[cur][v[cur][i]]));

		if (k) c[cur][v[cur][i]]-=k,c[v[cur][i]][cur]+=k,num-=k;

		if (num==0) break;

	}

	if (num) can[cur]=true;

	return tmp-num;

}

void maxedge(int cur,int num)

{

	if (num>f[cur]) f[cur]=num;

		else return;

	if (cur==t) return;

	for (unsigned i=0; i<v[cur].size(); i++)

		maxedge(v[cur][i],min(num,a[cur][v[cur][i]]));

}

int main()

{

	//freopen("data.in","rb",stdin);

	scanf("%d",&cas);

	while (cas--)

	{

		scanf("%d%d%d%d%d",&D,&n,&m,&s,&t);

		s++,t++;

		_init();

		while (m--)

		{

			scanf("%d%d%d",&U,&V,&W);

			U++,V++;

			/*

			if (tag[U]!=D || tag[V]!=D) a[U][V]=a[V][U]=c[U][V]=c[V][U]=0;

			if (tag[U]!=D) v[U].clear(),tag[U]=D;

			if (tag[V]!=D) v[V].clear(),tag[V]=D;

			*/

			c[U][V]+=W,a[U][V]+=W;

			v[U].push_back(V),v[V].push_back(U);

		}

		for (bfs(); d[s]<n; bfs()) ans+=dfs(s,Inf);

		for (int i=1; i<=n; i++) f[i]=cap;

		maxedge(s,Inf);

		printf("%d %.3f\n",D,ans*1.0/max(f[t],cap));

	}

	return 0;

}