# 最小生成樹
# 生成樹
生成樹條件:
- 一棵包含圖上所有點的樹，稱作該圖的生成樹
- 一張圖的生成樹可能會有很多種
- 完全連通圖才有生成樹 (不連通時，則稱為生成森林)
- 生成樹的權重為樹上每條邊的權重總和
至於最小生成樹就是權重和最小的生成樹
概念上就是這樣:
# 作法
- 圖上每一個點，各自是一棵最小生成子樹 MSS。
- 圖上所有邊，依照權重大小，由小到大排序。
- 嘗試圖上所有邊，作為最小生成樹（森林）的邊：
- 兩端點分別位於兩棵 MSS，也就是產生了橋：
- 用這條邊連結兩棵 MSS，合併成一棵 MSS。
- 這條邊是最小生成樹（森林）上的邊。
- 兩端點皆位於同一棵 MSS，也就是產生了環：
- 捨棄這條邊。
-> 所以需要使用到並查集喔～～
- 捨棄這條邊。
- 兩端點分別位於兩棵 MSS，也就是產生了橋：
# 例題
# c125: 00534 - Frogger
給定一個無向圖，求最小生成樹
這是一題最小生成樹的模板題，刻個幾次就熟了
#include <bits/stdc++.h> | |
using namespace std; | |
typedef long long ll; | |
struct Tree{ | |
int s,e,w; | |
bool operator<(Tree a)const{ | |
return a.w>w; | |
} | |
}; | |
int p[100000]; | |
int Find(int a){ | |
if (p[a] == a) return a; | |
else { | |
p[a] = Find(p[a]); | |
return p[a]; | |
} | |
} | |
void Kruskal(int n,int m) { | |
Tree dot[m]; | |
for(int i=0;i<n;i++) p[i]=i; | |
for (int i=0;i<m;i++) | |
cin >>dot[i].s>>dot[i].e>>dot[i].w; | |
sort(dot,dot+m); | |
ll ans=0,cnt = 0; | |
for (int i=0,x,y;i<m;i++) { | |
x = Find(dot[i].e); | |
y = Find(dot[i].s); | |
if(x==y) continue; | |
else { | |
p[y] = x; | |
ans +=dot[i].w; | |
cnt++; | |
} | |
} | |
if(cnt==n-1)cout<<ans; | |
else cout<<-1; | |
cout<<"\n"; | |
} | |
int main() { | |
int n,m; | |
while (cin >>n>>m) | |
Kruskal(n,m); | |
return 0; | |
} |
# b181: 2. 網路設計
給你一個字串形式的端點及路徑長，求出其的最小生成樹
第一行、輸出需要以字串形式輸出連結的狀況
第二行、輸出權重
難的部分就是如何處理其為字串的問題，一開始就將輸入的端點用兩個 map 對應:
字串對數字，數字對字串，每加入一個邊時就兩個端點加入 map 中，再開一個陣列紀錄圖形，最後再用使用 map 跟陣列做轉換就好了
#include<bits/stdc++.h> | |
using namespace std ; | |
struct str{ | |
int A,B,w,num; | |
bool operator<(str a)const{ | |
return a.w>w|| (a.w==w && a.num>num); | |
} | |
}; | |
map<string,int> Map ; | |
map<int,string> reMap ; | |
int fa[100] ; | |
str E[100] ; | |
int Ans[100] ; | |
int root(int x){ | |
if (fa[x]==x)return x ; | |
return root(fa[x]) ; | |
} | |
bool cmp(int a ,int b ){ | |
return E[a].A<E[b].A || (E[a].A==E[b].A && E[a].B<E[b].B) ; | |
} | |
int main(){ | |
int N ,M ; | |
while (~scanf("%d%d",&N ,&M )){ | |
Map.clear() ; | |
reMap.clear() ; | |
//input ------------- | |
char A[30],B[30] ; | |
for (int i=0 ;i<M ;i++ ){ | |
scanf("%s%s%d",&A ,&B ,&E[i].w ) ; | |
if (Map[ (string)A ]==0){ | |
char c ;int in ; | |
sscanf(A,"%c%d",&c ,&in ) ; | |
Map[(string)A]=in ; | |
reMap[in]=(string)A ; | |
} | |
E[i].A=Map[(string)A] ; | |
if (Map[ (string)B ]==0){ | |
char c ;int in ; | |
sscanf(B,"%c%d",&c ,&in) ; | |
Map[(string)B]=in ; | |
reMap[in]=(string)B ; | |
} | |
E[i].B=Map[(string)B] ; | |
E[i].num=i ; | |
} | |
sort(E,E+M) ; | |
//MST --------------- | |
for (int i=1 ;i<=N ;i++ )fa[i]=i ; | |
int Ansl=0 ,count=0 ; | |
for (int i=0 ;i<M ;i++ ){ | |
int a=root( E[i].A ) ; | |
int b=root( E[i].B ) ; | |
if (a==b)continue ; | |
fa[b]=a ; | |
Ans[Ansl++]=i ; | |
count+=E[i].w ; | |
} | |
//output ------------ | |
sort(Ans,Ans+Ansl,cmp) ; | |
for (int i=0 ;i<Ansl ;i++ ){ | |
cout << "(" << reMap[ E[ Ans[i] ].A ] <<" "<< reMap[ E[ Ans[i] ].B ] <<") " ; | |
} | |
printf("\n%d\n",count) ; | |
} | |
} |
