HDU 4240 Route Redundancy
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 ;
}
最新文章
- wpf 常见死锁方式
- Guava学习笔记目录
- 简单的IOS6和IOS7通过图片名适配
- Ubuntu离线安装包制作(转载)
- [转载]流式大数据处理的三种框架:Storm,Spark和Samza
- LINQ to Entities 不识别方法“System.String ToString()”,因此该方法无法转换为存储表达式。
- 基于iOS,Android的服务器证书失效检测
- [Cocos2d-x]代码段记录
- C语言学习之路,第一篇章。
- 如何解决JavaScript中0.1+0.2不等于0.3
- inner join 与 left join 之间的区别
- 【ZJOI2012】灾难
- day16-(listener&;filter)
- IO密集型 计算密集型
- C# GDI绘制仪表盘(纯代码实现)
- jQuery 初识
- jmeter接口测试1-参数化
- fatal: unable to auto-detect email address (got &#39;tim@newton.(none)&#39;)的解决方法
- [转]Activitys, Threads, &; Memory Leaks
- jpa的修改更新操作
热门文章
- jQuery练习总结(一)
- 王立平--TF卡
- windows下PTAM的编译
- 宝马男砍人不慎刀落反被杀 防卫过当or故意伤害(在生命受到威胁的情况下,已经很难判断对方意图了,而且假如于莫是老弱妇幼,可能现在死的就是于莫了)
- Linux下FFmpeg的安装编译过程【转】
- CentOS 7 NAT模式上网配置
- SpringMVC+uploadify3.2.1版实现附件上传功能(直接可以使用)
- .NET Core 开发:永远的Hello Word
- 又一个设计工具 Framer X Preview
- 深入浅出JDK动态代理(一)