ZeroJudge 解題筆記：b181. 2. 網路設計

作者：王一哲
日期：2025年12月8日


ZeroJudge 題目連結：b181. 2. 網路設計

解題想法

這題用自訂的併查集類別建立物件，依序從成本最低的邊開始測試，如果這條邊加上去之後，能夠使兩個節點所在的區塊連通，就要選用這條邊，記錄節點編號並更新總成本。 題目沒有說清楚的地方有三點：

1. 這題是多筆測資
2. n 只是節點編號的最大值，不見得有 n 個節點。
3. 節點的排序方式，讀取測資儲存邊的成本、節點時要按照測資的順序。輸出節點時要按照節點的編號由小到大排序，轉換成整數再比大小，不用管開頭的 W，兩個節點一組，先比較第一個節點，再比較第二個節點。輸出時如果按照字典序排序會出錯

   WA (line:3)
   您的答案為: (W10 W2) (W2 W3) (W3 W4) (W3 W5) (W3 W6)
   正確答案為: (W2 W3) (W3 W4) (W3 W5) (W3 W6) (W10 W2)
   

   如果按照第一個節點的編號數字排序也會出錯

   WA (line:3)
   您的答案為: (W2 W3) (W3 W5) (W3 W4) (W3 W6) (W10 W2)
   正確答案為: (W2 W3) (W3 W4) (W3 W5) (W3 W6) (W10 W2)
   

Python 程式碼

使用時間約為 19 ms，記憶體約為 3.5 MB，通過測試。

import sys
from functools import cmp_to_key

class DisjointSetUnion:
    def __init__(self, nodes):
        self.parent = {node: node for node in nodes}
        self.rank = {node: 0 for node in nodes}

    def rfind(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.rfind(self.parent[x])
        return self.parent[x]

    def union(self, u, v):
        root_u, root_v = self.rfind(u), self.rfind(v)
        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_v] > self.rank[root_u]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1
            return True
        return False

def mycmp(a, b):
    """ 為了輸出節點定義的比較式 """
    if int(a[0][1:]) == int(b[0][1:]):  # 如果第一個節點的編號相同
        if int(a[1][1:]) < int(b[1][1:]): return -1  # 第二個節點編號小的放前面
        elif int(a[1][1:]) > int(b[1][1:]): return 1
        else: return 0
    if int(a[0][1:]) < int(b[0][1:]): return -1  # 第一個節點編號小的放前面
    else: return 1

""" 處理多筆測資 """
result = []
lines = sys.stdin.readlines()
idx = 0
while idx < len(lines):
    """ 讀取測資 """
    n, m = map(int, lines[idx].split())  # 題目敘率不清，n 是可能的節點編號最大值，m 條邊
    idx += 1
    nodes = set()  # 所有節點，不見得有 n 個節點，要從邊的資料找節點
    edges = []  # 所有的邊
    for _ in range(m):  # 讀取 m 條邊
        line = lines[idx].split()
        idx += 1
        u, v = line[0], line[1]  # 節點 u, v 相連
        w = int(line[2])  # 邊的成本
        edges.append((w, u, v))  # (成本, 節點1, 節點2)，節點要按照測資的順序
        nodes.add(u)
        nodes.add(v)

    """ 用併查集找最低合併成本 """
    dsu = DisjointSetUnion(nodes)  # 建立併查集物件
    edges.sort()  # 依照成本由小到大排序
    cost = 0  # 總成本
    choose = []  # 選取的節點
    for w, u, v in edges:  # 依序讀取邊
        if dsu.union(u, v):  # 如果 u, v 可以合併
            cost += w  # 更新成本
            choose.append((u, v))  # 更新選取的節點
    """ 輸出答案 """
    choose.sort(key = cmp_to_key(mycmp))  # 輸出節點時，要按照節點編號大小排序，比數字
    res = []
    for u, v in choose:
        res.append(f"({u} {v})")
    result.append(" ".join(res) + "\n" + f"{cost:d}\n")
""" 一次輸出所有答案 """
sys.stdout.write("".join(result))

C++ 程式碼

使用時間約為 1 ms，記憶體約為 312 kB，通過測試。

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;

class DisjointSetUnion {
private:
    map<string, string> parent;
    map<string, int> rank;

public:
    DisjointSetUnion(set<string>& nodes) {
        for(auto node : nodes) {
            parent[node] = node;
            rank[node] = 0;
        }
    }

    string rfind(string x) {
        if (parent[x] == x) {
            return x;
        }
        parent[x] = rfind(parent[x]);
        return parent[x];
    }

    bool set_union(string u, string v) {
        string root_u = rfind(u), root_v = rfind(v);
        if (root_u != root_v) {
            if (rank[root_u] > rank[root_v]) {
                parent[root_v] = root_u;
            } else if (rank[root_v] > rank[root_u]) {
                parent[root_u] = root_v;
            } else {
                parent[root_v] = root_u;
                rank[root_u]++;
            }
            return true;
        }
        return false;
    }
};

struct Edge {
    string u, v;
    int w;

    Edge(string a, string b, int c) : u(a), v(b), w(c) {}
    Edge() : u("x"), v("y"), w(0) {}
};

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;
    while(cin >> n >> m) {
        /* 讀取測資 */
        vector<Edge> edges (m);
        set<string> nodes;
        for(int i=0; i<m; i++) {
            cin >> edges[i].u >> edges[i].v >> edges[i].w;
            nodes.insert(edges[i].u);
            nodes.insert(edges[i].v);
        }
        /* 用併查集找最低合併成本 */
        sort(edges.begin(), edges.end(), [](Edge a, Edge b) {
            return a.w < b.w;
        } );
        
        DisjointSetUnion dsu(nodes);
        int cost = 0;
        vector<vector<string>> choose;
        for(auto edge : edges) {
            if (dsu.set_union(edge.u, edge.v)) {
                cost += edge.w;
                choose.push_back({edge.u, edge.v});
            }
        }

        sort(choose.begin(), choose.end(), [](vector<string> a, vector<string> b) {
            if (stoi(a[0].substr(1)) == stoi(b[0].substr(1))) {
                return stoi(a[1].substr(1)) < stoi(b[1].substr(1));
            }
            return stoi(a[0].substr(1)) < stoi(b[0].substr(1));
        } );

        bool first_case = true;
        for(auto it : choose) {
            if (!first_case) cout << " ";
            first_case = false;
            cout << "(" << it[0] << " " << it[1] << ")";
        }
        cout << "\n" << cost << "\n";
    }
    return 0;
}