Route Redundancy
This problem will be judged on HDU. Original ID: 4240
64-bit integer IO format: %I64d Java class name: Main
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.
Input
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.
Output
Sample Input
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
Sample Output
1 1.667
Source
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <cstdlib>
#include <string>
#include <set>
#include <stack>
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = ;
struct arc{
int to,flow,next;
arc(int x = ,int y = ,int z = -){
to = x;
flow = y;
next = z;
}
};
arc e[maxn*];
int head[maxn],d[maxn],cur[maxn],tot,s,t,n;
void add(int u,int v,int flow){
e[tot] = arc(v,flow,head[u]);
head[u] = tot++;
e[tot] = arc(u,,head[v]);
head[v] = tot++;
}
bool bfs(){
queue<int>q;
for(int i = ; i <= n; ++i) d[i] = -;
q.push(s);
d[s] = ;
while(!q.empty()){
int u = q.front();
q.pop();
for(int i = head[u]; ~i; i = e[i].next){
if(e[i].flow && d[e[i].to] == -){
d[e[i].to] = d[u] + ;
q.push(e[i].to);
}
}
}
return d[t] > -;
}
int dfs(int u,int low){
if(u == t) return low;
int tmp = ,a;
for(int &i = cur[u]; ~i; i = e[i].next){
if(e[i].flow && d[e[i].to] == d[u] + && (a = dfs(e[i].to,min(e[i].flow,low)))){
e[i].flow -= a;
e[i^].flow += a;
tmp += a;
low -= a;
break;
}
}
if(!tmp) d[u] = -;
return tmp;
}
bool vis[maxn];
int maxcap;
void dfs2(int u){
vis[u] = true;
for(int i = head[u]; ~i; i = e[i].next){
if(!vis[e[i].to]){
maxcap = max(maxcap,e[i^].flow);
if(e[i^].flow == ){
cout<<u<<" "<<e[i].to<<endl;
}
dfs2(e[i].to);
}
}
}
int main(){
int p,cs,m,u,v,cap;
scanf("%d",&p);
while(p--){
scanf("%d %d %d %d %d",&cs,&n,&m,&s,&t);
memset(head,-,sizeof(head));
for(int i = tot = ; i < m; ++i){
scanf("%d %d %d",&u,&v,&cap);
add(u,v,cap);
}
int ans = ,o;
maxcap = ;
while(bfs()){
memcpy(cur,head,sizeof(head));
o = dfs(s,INF);
ans += o;
maxcap = max(maxcap,o);
}
memset(vis,false,sizeof(vis));
//maxcap = 0;
//dfs2(s);
printf("%d %.3f\n",cs,ans*1.0/maxcap);
//cout<<ans<<" "<<maxcap<<endl;
}
return ;
}