題目： UVa - 11631 - Dark roads

題目說明

在一個國家中，城市間有很多條路相連，在路上每一公尺的路燈花費是 1，現在想要使路燈花費最少，且從任意的一個城市到另一個城市可以找到一條都開著路燈的路徑。

Input： 每組測資的第一行為兩個整數 m、n，分別代表城市的數量及路的數量，若兩者皆為 0 則結束。後面 n 行，每行有三個整數 u、v、w，表示有一條 (u, v) 的路，且長 w 公尺。

Output： 輸出所有路都開路燈的花費減去最少的花費。

解題思路

這個解法需要有 Union Find 及 Kruskcal 演算法的概念。

先讀取測資同時記錄所有路燈的花費，之後建圖，使用 Union Find 及 Kruskcal 找出最小生成樹，樹的邊即是路燈花費最少的開法，所以在加入一條邊時減去花費，最後的結果即是答案。

參考解法

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
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// reference: https://ppt.cc/fmw7gx

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

struct edge
{
    int u;
    int v;
    int w;

    // 根據權重排序
    bool operator<(const edge& r) { return w < r.w; }
};

// data
int cost;
vector<edge> edges;
int parents[200001]; // 每個點的 parent
int ranks[200001];

void init(int n)
{
    cost = 0;
    edges.clear();
    // 一開始每個節點的 parent 都是自己，而 rank 皆為 0
    for (int i = 0; i <= n; ++i) parents[i] = i, ranks[i] = 0;
}

int Find(int p) { return p == parents[p] ? p : parents[p] = Find(parents[p]); }

bool Union(int x, int y)
{
    int rx = Find(x), ry = Find(y);

    // 如果 x 跟 y 的 root 一樣，表示 x 和 y 接起會造成環
    if (rx == ry) return false;

    // 將 rank 較小的接到 rank 較大的樹下面，因為這樣後面 Find 時消耗較小
    if (ranks[rx] > ranks[ry]) parents[ry] = rx;
    else if (ranks[rx] < ranks[ry]) parents[rx] = ry;
    else parents[ry] = rx, ++ranks[rx];

    return true;
}

void kruskcal(int n)
{
    int j = 0;
    for (auto& [u, v, w] : edges)
    {
        if (j == n - 1) break;
        
        // 若 u、v 接起會造成環則不接
        if (!Union(u, v)) continue;

        // 將總花費減去實際花費
        cost -= w;
        ++j;
    }
}

int main()
{
    int m, n;

    while (cin >> m >> n && !(!n && !m))
    {
        init(m);

        while (n--)
        {
            int u, v, w;
            cin >> u >> v >> w;
            cost += w; // 先將總花費加起來
            edges.push_back({ u, v, w });
        }

        sort(edges.begin(), edges.end());

        kruskcal(m);

        cout << cost << '\n';
    }
}

參考資料

[UVA] 11631 - Dark roads @ 程式碼備份區 :: 痞客邦 ::