首页 > ACM题库 > HDU-杭电 > HDU 4240-Route Redundancy-Dijkstra-[解题报告]HOJ
2015
05-23

HDU 4240-Route Redundancy-Dijkstra-[解题报告]HOJ

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
题意:除了要求出最大流之外,还要求另一个最小车辆的最大值M,
最小车辆的定义是 在一条可行流的路径上最小的边权(初始边权)

技巧在与求增广路径的方法,主要是第一次找的方法,因为M == 第一次可行的具有最大压入流量的增广路径的压入的流量
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;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/cscj2010/article/details/7935682