zoj3792--Romantic Value(最大流+最小割，求解割边)

Farmer John is a diligent man. He spent a lot of time building roads between his farms. From his point of view, every road is romantic because the scenery along it is very harmonious and beautiful. Recently, John is immersed in poetry, he wants stay alone and enjoy the wonderful words. But his little brother always disturbs him. This night, fortunately, his little brother does not stay the same farm with him. So, he wants to destroy some roads to keep himself quiet for a few days(then no route exist between John and his brother). Of course, John love his romantic roads, so he want to separate him and his brother with least romantic cost.

There are N farms(numbered from 1 to N) and M undirected roads each with a romantic value c(indicate how much Farmer John loves it). Now John stays in farm p and his little brother stay in farm q. John wants to first minimize the romantic value lost, then to destroy as few roads as possible. Help him to calculate the ratio of [sum of the remainder roads‘ value]/[the amount of removed roads](not necessary to maximisation this ratio) when he achieves his goal.

Input

The first line is a single integer T, indicate the number of testcases. Then follows T testcase. For each testcase, the first line contains four integers N M p q(you can assume p and q are unequal), then following M lines each contains three integer a b c which means there is an undirected road between farm a and farm b with romantic value c. (2<=N<=50, 0<=M<=1000, 1<=c<1000, 1<=p,q<=N)

Output

For each test case, print the ratio in a single line(keep two decimal places). If p and q exist no route at the start, then output "Inf".

Sample Input

1
4 5 1 4
1 2 1
1 3 1
2 4 2
3 4 2
2 3 1

Sample Output

2.50

给出n个庄园，m条无向路，每一个路有浪漫值，一个人在p点，一个人在q点，摧毁几条路，使得两个人不能走到一起，求 剩余的浪漫值/摧毁的路数

最小割问题，每条路是无向路，所以建i到j的正向边反向边，j到i的正向边反向边。求解出最大流，由最大流最小割定理，得到最小割的值就是最大流的值max_flow，但是如果求解最小割的边数，最小割的边一定是满流的边，满流的边不一定是最小割的边。求解方法

将所有满流的边的值重置为1，不是满流的重置为INF，反向边重置为0，再进行一次最大流，求解出的最大流的流量，也就是最小割需要的边数

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
struct node
{
    int v , w ;
    int next ;
} p[10000];
int head[60] , cnt , l[60] ;
queue <int> Q ;
void add(int u,int v,int w)
{
    p[cnt].v = v ;
    p[cnt].w = w ;
    p[cnt].next = head[u] ;
    head[u] = cnt++ ;
    p[cnt].v = u ;
    p[cnt].w = 0 ;
    p[cnt].next = head[v] ;
    head[v] = cnt++ ;
}
int bfs(int s,int t)
{
    int u , v , i ;
    memset(l,-1,sizeof(l));
    l[s] = 0 ;
    while( !Q.empty() )
        Q.pop();
    Q.push(s);
    while( !Q.empty() )
    {
        u = Q.front();
        Q.pop();
        for(i = head[u] ; i != -1 ; i = p[i].next)
        {
            v = p[i].v ;
            if( l[v] == -1 && p[i].w )
            {
                l[v] = l[u] + 1 ;
                Q.push(v);
            }
        }
    }
    if( l[t] > 0 )
        return 1 ;
    return 0 ;
}
int dfs(int u,int t,int min1)
{
    if(u == t)
        return min1 ;
    int flow = 0 , i , a , v ;
    for( i = head[u] ; i != -1 ; i = p[i].next )
    {
        v = p[i].v ;
        if( l[v] == l[u]+1 && p[i].w && ( a = dfs(v,t,min(min1,p[i].w) ) ) )
        {
            p[i].w -= a ;
            p[i^1].w += a ;
            flow += a ;
            min1 -= a ;
        }
    }
    if( flow )
        return flow;
    l[u] = -1 ;
    return 0;
}
int main()
{
    int t , n , m , u , v , i , j , x , max_flow , num , sum ;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d %d %d %d", &n, &m, &u, &v) ;
        cnt = 0 ;
        max_flow = 0 ;
        sum = 0 ;
        memset(head,-1,sizeof(head));
        while(m--)
        {
            scanf("%d %d %d", &i, &j, &x);
            add(i,j,x);
            add(j,i,x);
            sum += x ;
        }
        while( bfs(u,v) )
        {
            max_flow += dfs(u,v,INF);
        }
        if(max_flow == 0)
        {
            printf("Inf\n");
            continue ;
        }
        for(i = 0 ; i < cnt ; i += 2)
        {
            if( p[i].w == 0 )
                p[i].w = 1 ;
            else
                p[i].w = INF ;
            p[i^1].w = 0 ;
        }
        num = 0 ;
        while( bfs(u,v) )
        {
            num += dfs(u,v,INF) ;
        }
        printf("%.2lf\n", (sum-max_flow)*1.0/num) ;
    }
    return 0;
}

zoj3792--Romantic Value(最大流+最小割，求解割边),布布扣,bubuko.com

zoj3792--Romantic Value(最大流+最小割，求解割边)

原文：http://blog.csdn.net/winddreams/article/details/38677855