e586 - 01208 - Oreon
題目描述
題目描述了一個城市間隧道安全問題，目標是找到一組需要保護的隧道，使得所有城市保持連通，並且保護這些隧道所需的總人員數量最小。輸入是一個城市間隧道安全圖，圖中的數字表示保護該隧道所需的安全人員數量。
解題思路
這題可以建模為最小生成樹 (Minimum Spanning Tree) 的變形。城市可以看作圖的節點，隧道可以看作圖的邊，邊的權重是保護該隧道所需的安全人員數量。目標是找到一棵最小權重生成樹，使得所有城市連通。
程式碼使用 Kruskal 演算法來尋找最小生成樹。Kruskal 演算法的核心是：
- 將所有邊按照權重從小到大排序。
- 從權重最小的邊開始，依次考慮每一條邊。
- 如果加入該邊不會形成環，則將該邊加入到最小生成樹中。
- 重複步驟 2 和 3，直到所有節點都連通。
程式碼使用 Union-Find 資料結構來判斷加入某條邊是否會形成環。Union-Find 資料結構可以高效地判斷兩個節點是否在同一個連通分量中。如果兩個節點在同一個連通分量中，則加入它們之間的邊會形成環。
複雜度分析
- 時間複雜度: O(E log E)，其中 E 是邊的數量。排序邊需要 O(E log E) 的時間，Union-Find 演算法的每個操作需要 O(α(N)) 的時間，其中 α(N) 是反阿克曼函數，可以看作常數。因此，Union-Find 演算法的總時間複雜度是 O(E α(N))，可以近似為 O(E)。
- 空間複雜度: O(N + E)，其中 N 是節點的數量，E 是邊的數量。需要 O(N) 的空間來儲存 Union-Find 資料結構，需要 O(E) 的空間來儲存邊。
程式碼
#include <iostream>
using namespace std;
int a[27][27],all[27];
int fa(int no){
if(all[no]==no)return no;
all[no]=fa(all[no]);
return fa(all[no]);
}
bool jg(int no){
int s=0;
for(int i=0;i<no;++i)
if(all[i]==i){
if(s==1)return 0;
s=1;
}
return 1;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int t,n;
char c;
cin >> t;
for(int ca=1;ca<=t;++ca){
cin >> n;
for(int i=0;i<26;++i)
for(int j=0;j<26;++j)
a[i][j]=0;
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
cin >> a[i][j];
if(j<n-1)cin >> c;
}
}
cout << "Case " << ca << ":\n";
for(int i=0;i<26;++i)
all[i]=i;
while(1){
if(jg(n))break;
int mn=1000000,x=-1,y=-1;
for(int i=0;i<n;++i)
for(int j=i+1;j<n;++j)
if(a[i][j]&&a[i][j]<mn&&fa(all[i])!=fa(all[j])){
mn=a[i][j];
x=i;
y=j;
}
char ax=x+'A',ay=y+'A';
cout << ax << "-" << ay << " " << mn << "\n";
a[x][y]=a[y][x]=0;
int mnn=min(fa(all[x]),fa(all[y]));
for(int i=0;i<n;++i)
if(fa(all[i])==fa(all[x])||fa(all[i])==fa(all[y]))
all[i]=mnn;
}
}
}