1234 RACING

題目連結

題目敘述

聖安德烈路是 F1 賽道的一部分（Kenny Pek，Piccom）

新加坡將在 2008 年舉辦一場一級方程式賽車（F1）比賽
這場比賽將在一條長達 5.067 公里的街道賽道上舉行，賽道包含 14 個左彎和 10 個右彎
隨著 F1 比賽的接近，非法的夜間街頭賽車活動也逐漸增加
這些非法賽車通常會繞著特定的街道賽道跑好幾圈

當局希望部署一套新的車輛監控系統來抓捕這些在聖安德烈路（F1 賽道的一部分）非法賽車的駕駛人
該系統由安裝在各條道路上的多個攝影機所組成
為了使此系統有效，必須在每一條可能構成賽道的道路上至少安裝一台攝影機

新加坡的道路系統可以表示為一系列的交叉路口（junctions）與雙向道路（roads）（請參考圖 5）
一條可能的賽車賽道是從某個交叉路口出發，經過三條或更多的道路，最後回到起點交叉路口
賽道中的每一條道路只能以單一方向行駛一次

你的任務是撰寫一個程式，計算車輛監控攝影機的最佳安裝位置
你將獲得一個需要監控的連通道路網路的描述，內容包含道路與交叉路口的資訊
交叉路口的編號如圖 5 中的大數字所示，攝影機只能安裝在道路上（不能安裝在交叉路口上）

安裝攝影機的成本依照道路而異
圖 5 中道路旁的小數字表示在該條道路上安裝攝影機的成本
你的工作是選擇一組道路，在確保每一條可能的賽道（即道路網路中的迴路）上至少有一台攝影機的前提下，使安裝攝影機的總成本最小

輸入說明

輸入的第一行為一個整數 c，表示資料集的數量，接著是 c 組資料集，最後以一行包含數字 0 結尾

每組資料集的第一行包含兩個正整數 n 和 m，以空白分隔，分別表示交叉路口數量與道路數量
你可以假設 0 < n < 10000 且 0 < m < 100000。為簡化起見，交叉路口從 1 到 n 編號

接下來的 m 行，每行描述一條道路，包含三個正整數，分別為兩個不同的交叉路口編號與在該道路上安裝攝影機的成本
攝影機的安裝成本介於 1 到 1000 之間

輸出說明

對每組資料集，輸出一行，表示建立車輛監控系統以涵蓋所有可能賽道所需的最小總成本。

附註

範例資料集對應圖 5 所示的情況
圖中兩個攝影機所示的位置可以以最小成本監控所有賽道
由於每台攝影機的成本為 3，因此總成本為 6

解題思路

既然每個迴路都需要安裝一個監視器
可以使用 Kruskal 建最大生成樹
最後剩下的邊即為每一個迴路中成本最小的道路
將其相加即可計算出整組道路需要的最小總成本

程式碼

#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()

vector<int> anc;

int Find(int x) {
    return (anc[x] == x ? x : anc[x] = Find(anc[x]));
}

bool Union(int a, int b) {
    int fa = Find(a), fb = Find(b);
    if (fa == fb) return true;
    return anc[fb] = fa, false;
}

int  main() {
    int t; while (cin >> t, t) {
        while (t--) {
            int n, m; cin >> n >> m;
            vector<tuple<int, int, int>> v;
            anc.resize(n+1);
            iota(all(anc), 0); // iota 即為從頭到尾依序放置 i, i+1, i+2，這裡 i 為 0，用於初始化 union-find 的祖先陣列

            // 我很想用 structured binding，但考慮到 CPE 是用 C++ 14 的版本問題，所以還是土法煉鋼好了
            while (m--) {
                int a, b, w;
                cin >> a >> b >> w;
                v.push_back({w, a, b});
            }

            sort(all(v), greater<tuple<int, int, int>>());
            int ans = 0;
            for (auto &i : v) {
                int a, b, w;
                tie(w, a, b) = i;
                if (Union(a, b)) ans += w;
            }
            cout << ans << '\n';
        }
    }
}