Problem Solving►UVa

UVa 10480 - Sabotage

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址

求出把首都(1)和最大城市(2)切斷聯絡的最小花費。

Solution

Ref:
http://www.csie.ntnu.edu.tw/~u91029/Cut.html#2
http://www.csie.ntnu.edu.tw/~u91029/Flow.html#2

最大流/最小割問題。

先把最大流求出後，利用最後一次 BFS 的結果從源點去找出有哪些流量滿的，也就是首先要被切斷的。
(不用去處理滿後繼續流的路線，只找首先被割的即可)

做法就是窮舉每條邊，看哪一段前面本來有流量，但應這一段已經溢滿了，導致無法繼續流。
此時這條就是其中一個最小割。

Code

UVa 10480
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define N 51
using namespace std;

int adj[N][N]; //residue capacity
int parent[N];
int flow[N]; //邊計算流量瓶頸
int n;
int BFS(int s, int t)
{
    memset(parent, 0, sizeof parent);
    memset(flow, 0, sizeof flow);

    queue<int> Q;
    Q.push(s);
    parent[s] = s;
    flow[s] = 1e9;

    while (!Q.empty())
    {
        int now = Q.front();
        Q.pop();
        for (int i = 1; i <= n; ++i)
        {
            if (adj[now][i] > 0 && !parent[i])
            {
                parent[i] = now;

                flow[i] = min(adj[now][i], flow[now]);
                if (i == t)
                    return flow[i];

                Q.push(i);
            }
        }
    }

    return 0; //無任何擴充路徑，流量為零
}
int main()
{
    int m;
    int capacity[N][N] = {}; //original capacity
    while (scanf("%d%d", &n, &m) && (n || m))
    {
        int u, v, c, f;
        for (int i = 0; i < m; ++i)
        {
            scanf("%d%d%d", &u, &v, &c);
            capacity[u][v] = capacity[v][u] = adj[v][u] = adj[u][v] = c;
        }

        //maximum flow
        while ((f = BFS(1, 2)) != 0)
        {
            for (int from = parent[2], to = 2; from != to; from = parent[to = from])
            {
                adj[from][to] -= f;
                adj[to][from] += f;
            }
        }

        //find minimum s-t cut
        //利用最後一次 BFS 的 flow[] (這邊用意等同於 visited)
        for (int i = 1; i <= n; ++i) //窮舉源點側的，也就是 x -> i 這段是有流量的
            if (flow[i] > 0)
                for (int j = 1; j <= n; ++j)        //窮舉匯點側的，也就是 i -> j 這段沒流量
                    if (!flow[j] && capacity[i][j]) //並確定 i -> j 原本有邊，現在才被割掉
                        printf("%d %d\n", i, j);

        putchar('\n');

        //init
        for (int i = 1; i <= n; ++i)
        {
            memset(adj[i], 0, sizeof adj[i]);
            memset(capacity[i], 0, sizeof capacity[i]);
        }
    }

    return 0;
}