2015
05-23

# Route Redundancy

A city is made up exclusively of one-way steets.each street in the city has a capacity,which is the minimum of the capcities of the streets along that route.

The redundancy ratio from point A to point B is the ratio of the maximum number of cars that can get from point A to point B in an hour using all routes simultaneously,to the maximum number of cars thar can get from point A to point B in an hour using one route.The minimum redundancy ratio is the number of capacity of the single route with the laegest capacity.

The first line of input contains asingle integer P,(1<=P<=1000),which is the number of data sets that follow.Each data set consists of several lines and represents a directed graph with positive integer weights.

The first line of each data set contains five apace separatde integers.The first integer,D is the data set number. The second integer,N(2<=N<=1000),is the number of nodes inthe graph. The thied integer,E,(E>=1),is the number of edges in the graph. The fourth integer,A,(0<=A<N),is the index of point A.The fifth integer,B,(o<=B<N,A!=B),is the index of point B.

The remaining E lines desceibe each edge. Each line contains three space separated in tegers.The First integer,U(0<=U<N),is the index of node U. The second integer,V(0<=v<N,V!=U),is the node V.The third integer,W (1<=W<=1000),is th capacity (weight) of path from U to V.

The first line of input contains asingle integer P,(1<=P<=1000),which is the number of data sets that follow.Each data set consists of several lines and represents a directed graph with positive integer weights.

The first line of each data set contains five apace separatde integers.The first integer,D is the data set number. The second integer,N(2<=N<=1000),is the number of nodes inthe graph. The thied integer,E,(E>=1),is the number of edges in the graph. The fourth integer,A,(0<=A<N),is the index of point A.The fifth integer,B,(o<=B<N,A!=B),is the index of point B.

The remaining E lines desceibe each edge. Each line contains three space separated in tegers.The First integer,U(0<=U<N),is the index of node U. The second integer,V(0<=v<N,V!=U),is the node V.The third integer,W (1<=W<=1000),is th capacity (weight) of path from U to V.

1
1 7 11 0 6
0 1 3
0 3 3
1 2 4
2 0 3
2 3 1
2 4 2
3 4 2
3 5 6
4 1 1
4 6 1
5 6 9

1 1.667

/**
[最大流] hdu 4240 Route Redundancy

lowc[i]表示以i为终点的包含M的压入量，注意更新的方式，类似prim或是dijkstra算法
*/
#include <stdio.h>
#include <queue>
#include <string.h>
#include <algorithm>

using namespace std;

typedef pair<int,int >  Pii;
#define MK make_pair
const int N = 101,INF = 100000000;
int g[N][N],pre[N],n;

int path(int s,int t)
{
int lowc[N],vis[N],i,u,v,dd = INF;
priority_queue < Pii > que;
Pii p;
memset(vis,0,sizeof(vis));
memset(pre,-1,sizeof(pre));
for(i = 0; i < n; ++i)
lowc[i] = INF;
que.push(MK(INF,s));
while(!que.empty())
{
u = que.top().second;
dd = que.top().first;
que.pop();
if(u == t)
return lowc[t];
if(vis[u])
continue;
vis[u] = 1;
for(i = 0; i < n; ++i)
if(!vis[i] && g[u][i] > 0)
{

if(lowc[i] == INF)
lowc[i] = min(lowc[u],g[u][i]);
else
{
if(g[u][i] < lowc[u])
lowc[i] = max(lowc[i],g[u][i]);
else
lowc[i] = lowc[u];
}
pre[i] = u;
que.push(MK(lowc[i],i));
}
}
return 0;
}
void maxFlow(int s,int t)
{
int first = 1,res = 0,minc = INF,i,d;
while(1)
{

d = path(s,t);
if(!d)
break;
if(first)
{
minc = d;
first = 0;
}
res += d;
for(i = t; i != s; i = pre[i])
{
g[pre[i]][i] -= d;
g[i][pre[i]] += d;
}
}
printf("%.3lf\n",res * 1.0 / minc);
}
int main()
{
int cas,a,b,i,j,cp,tt,e;
scanf("%d",&tt);
while(tt--)
{
scanf("%d%d%d%d%d",&cas,&n,&e,&a,&b);
memset(g,0,sizeof(g));
while(e--)
{
scanf("%d%d%d",&i,&j,&cp);
g[i][j] += cp;
}
printf("%d ",cas);
maxFlow(a,b);
}
return 0;
}