作者：王一哲
日期：2025年12月8日
ZeroJudge 題目連結：
b181. 2. 網路設計
解題想法
這題用自訂的併查集類別建立物件，依序從成本最低的邊開始測試，如果這條邊加上去之後，能夠使兩個節點所在的區塊連通，就要選用這條邊，記錄節點編號並更新總成本。
題目沒有說清楚的地方有三點：
- 這題是多筆測資
- n 只是節點編號的最大值，不見得有 n 個節點。
- 節點的排序方式，讀取測資儲存邊的成本、節點時要按照測資的順序。輸出節點時要按照節點的編號由小到大排序，轉換成整數再比大小，不用管開頭的 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))
