最小生成樹對應的問題都是無向圖
最小生成樹演演算法 :
捋清演演算法思路 , 弄清楚演演算法的流程 , 不是死記模版
集合 s 表示當前已經在連通塊中的點
步驟 :
模版 :
給定一個n個點m條邊的無向圖 , 圖中可能存在重邊和自環 , 邊權可能為負數.
求最小生成樹的樹邊權重之和 , 如果最小生成樹不存在則輸出 impossible.
1 <= n <= 500 , 1 <= m <= 10^5
輸入樣例 :
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
輸出樣例 :
6
點到集合的距離 : 點到集合中的點的所有邊中最短的那條邊
最小生成樹中, 沒有環 , 因此正邊和負邊都可以
程式碼如下 :
// 樸素版 Prim演演算法 :
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std ;
const int N = 510 , INF = 0x3f3f3f3f ;
int dist[N] ; bool st[N] ; int n , m ; int g[N][N] ; // 稠密圖 , 鄰接矩陣儲存
int prim()
{
memset(dist,0x3f,sizeof dist) ; // 初始狀態 , 所有點到集合的距離均為無窮大
int res = 0 ; // res 記錄最小生成樹的各邊的權值的和
// n 個點 , 迭代 n 次
for(int i = 0;i < n;i ++ )
{
int t = -1 ;
// 從集合外的點集中找到距離當前集合距離最短的點 , 第一次時隨機選擇
for(int j = 1;j <= n;j ++ )
{
if(!st[j] && (t == -1 || dist[t] > dist[j]))
{
t = j ;
}
}
if(i && dist[t] == INF) return -1 ; // 如果當前不是第一個點且其到集合的距離為INF,則該圖不連通
if(i) res += dist[t] ;
// 注意 : 這裡可能存在自環的情況 , 所以應該先累加邊的權值 , 再進行更新
for(int j = 1;j <= n;j ++ ) dist[j] = min(dist[j] , g[t][j]) ; // 更新集合外的點到集合的距離
st[t] = true ; // 將點 t 加入到集合當中
}
return res ;
}
int main()
{
scanf("%d%d",&n,&m) ;
memset(g,0x3f,sizeof g) ;
while (m -- )
{
int a , b , c ; scanf("%d%d%d",&a,&b,&c) ;
g[a][b] = g[b][a] = min(g[a][b] , c) ; // 存在重邊 , 取最小值
}
int t = prim() ;
if(t == -1) puts("impossible") ;
else printf("%d \n",t) ;
return 0 ;
}
步驟 :
模版 :
給定一個n個點m條邊的無向圖 , 圖中可能存在重邊和自環 , 邊權可能為負數.
求最小生成樹的樹邊權重之和 , 如果最小生成樹不存在則輸出 impossible.
不需存圖 , 直接開一個結構體存邊即可
輸入樣例 :
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
輸出樣例 :
6
程式碼如下 :
// Kruskal 演演算法 :
#include <iostream>
#include <algorithm>
using namespace std ;
const int N = 100010 ;
int n , m ; int p[N] ;
struct Edge{
int a , b , w ;
bool operator< (const Edge & W) const // 過載小於號 , 使排序的時候按w的值排序
{
return w < W.w ;
}
}edges[N];
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]) ;
return p[x] ;
}
int main()
{
scanf("%d%d",&n,&m) ;
for(int i = 0;i < m;i ++ )
{
int a , b , w ; scanf("%d%d%d",&a,&b,&w) ;
edges[i] = {a , b , w} ;
}
sort(edges , edges + m) ;
for(int i = 1;i <= n;i ++ ) p[i] = i ; // 初始化並查集陣列
int res = 0 , cnt = 0 ;
for(int i = 0;i < m;i ++ )
{
int a = edges[i].a , b = edges[i].b , w = edges[i].w ;
a = find(a) , b = find(b) ;
if(a != b)
{
p[a] = b ;
res += w ;
cnt ++ ;
}
}
if( cnt != n - 1 ) puts("impossible") ;
else printf("%d \n",res) ;
return 0 ;
}
簡介 : 二分圖,又稱二部圖,英文名叫 Bipartite graph。
節點由兩個集合組成,且兩個集合內部沒有邊的圖。
換言之,存在一種方案,將節點劃分成滿足以上性質的兩個集合。
*性質 : 二分圖不存在長度為奇數的環 充分必要
因為每一條邊都是從一個集合走到另一個集合,只有走偶數次才可能回到同一個集合。
時間複雜度 : O ( n + m ) 線性 . 類似於dfs
如果在染色過程中出現矛盾 --> 存在奇數環 , 不是二分圖
反之 , 則是二分圖
模版 : 染色法判定二分圖 :
給定一個n個點m條邊的無向圖 ,圖中可能存在重邊或自環,判斷這個圖是否是二分圖
輸入樣例 :
4 4
1 3
1 4
2 3
2 4
輸出樣例 :
Yes
程式碼如下 :
// 二分圖的染色法 :
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std ;
const int N = 100010 , M = N << 1 ;
int h[N] , e[M] , ne[M] , idx ; int color[N] ;
int n , m ;
void add(int a,int b)
{
e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ;
}
bool dfs(int u,int c)
{
color[u] = c ; // 給 u 點染色
for(int i = h[u] ; i != -1;i = ne[i])
{
int j = e[i] ;
if (!color[j])
{
if(!dfs(j,3 - c)) // 因為 j 是u 的相鄰點 , 所以給其染色時要與u不一樣 , 3-u即可
{
return false ;
}
}
else if (color[j] == c) return false ; // 如果 j 的顏色與 u相同,不行,因為它們是相鄰點
}
return true ;
}
int main()
{
scanf("%d%d",&n,&m) ;
memset(h,-1,sizeof h) ;
while (m -- )
{
int a , b ; scanf("%d%d",&a,&b) ;
add(a,b) ; add(b,a) ;
}
bool flag = true ;
for(int i = 1;i <= n;i ++ )
{
if(!color[i])
{
if(!dfs(i,1))
{
flag = false ; break ;
}
}
}
if(!flag) puts("No") ;
else puts("Yes") ;
return 0 ;
}
時間複雜度 : O ( mn ) , 實際執行時間一般遠小於 O( mn )
匹配:在圖論中,一個「匹配」(matching)是一個邊的集合,其中任意兩條邊都沒有公共頂點。
交替路:從一個未匹配點出發,依次經過非匹配邊、匹配邊、非匹配邊…形成的路徑叫交替路。
增廣路:從一個未匹配點出發,走交替路,如果途徑另一個未匹配點(出發的點不算),則這條交替路稱為增廣路(agumenting path)。
增廣路有一個重要特點:非匹配邊比匹配邊多一條。因此,研究增廣路的意義是改進匹配。只要把增廣路中的匹配邊和非匹配邊的身份交換即可。由於中間的匹配節點不存在其他相連的匹配邊,所以這樣做不會破壞匹配的性質。
我們可以通過不停地找增廣路來增加匹配中的匹配邊和匹配點。找不到增廣路時,達到最大匹配(這是增廣路定理)。匈牙利演演算法正是這麼做的。
匈牙利樹一般由 BFS 構造(類似於 BFS 樹)。從一個未匹配點出發執行 BFS(唯一的限制是,必須走交替路),直到不能再擴充套件為止。
匈牙利樹要求所有葉子節點均為匹配點.
匈牙利演演算法 : 求解一個圖中的最大匹配
匈牙利演演算法的要點如下
- 從左邊第 1 個頂點開始,挑選未匹配點進行搜尋,尋找增廣路。
- 如果經過一個未匹配點,說明尋找成功。更新路徑資訊,匹配邊數 +1,停止搜尋。
- 如果一直沒有找到增廣路,則不再從這個點開始搜尋。事實上,此時搜尋後會形成一棵匈牙利樹。我們可以永久性地把它從圖中刪去,而不影響結果。
- 由於找到增廣路之後需要沿著路徑更新匹配,所以我們需要一個結構來記錄路徑上的點。DFS 版本通過函數呼叫隱式地使用一個棧,而 BFS 版本使用
prev
陣列。效能比較
兩個版本的時間複雜度均為O(V⋅E)O(V⋅E)。DFS 的優點是思路清晰、程式碼量少,但是效能不如 BFS。我測試了兩種演演算法的效能。對於稀疏圖,BFS 版本明顯快於 DFS 版本;而對於稠密圖兩者則不相上下。在完全亂資料 9000 個頂點 4,0000 條邊時前者領先後者大約 97.6%,9000 個頂點 100,0000 條邊時前者領先後者 8.6%, 而達到 500,0000 條邊時 BFS 僅領先 0.85%。
補充定義和定理:
最大匹配數:最大匹配的匹配邊的數目
最小點覆蓋數:選取最少的點,使任意一條邊至少有一個端點被選擇
最大獨立數:選取最多的點,使任意所選兩點均不相連
最小路徑覆蓋數:對於一個 DAG(有向無環圖),選取最少條路徑,使得每個頂點屬於且僅屬於一條路徑。路徑長可以為 0(即單個點)。
定理1:最大匹配數 = 最小點覆蓋數(這是 Konig 定理)
定理2:最大匹配數 = 最大獨立數
定理3:最小路徑覆蓋數 = 頂點數 - 最大匹配數
選自 : https://www.renfei.org/blog/bipartite-matching.html
模版 :
給定一個二分圖 , 其中左半部包含 n1 個點 ( 編號1~n1 ) , 右半部分包含 n2 個點 (編號 1 ~ n2) , 二分圖共包含 m 條邊. 求出二分圖的最大匹配數.
輸入樣例 :
2 2 4
1 1
1 2
2 1
2 2
輸出樣例 :
2
程式碼如下 :
// Huagarian 匈牙利演演算法 :
// hungarian(匈牙利演演算法) :
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std ;
const int N = 510 , M = 100010 ;
int n1 , n2 , m ;
int h[N] , e[M] , ne[M] , idx ;
int match[N] ; // 右邊的點所對應的左邊的點
bool st[N] ; // 判重 , 保證每個點只匹配一個點 , 否則會無限迴圈
void add(int a,int b)
{
e[idx] = b , ne[idx] = h[a] , h[a] = idx ++ ;
}
// 寫迭代遞迴類演演算法時 , 相信其能完成我們給定的功能 , 不用去繞進去想
bool find(int x)
{
for(int i = h[x];i != -1;i = ne[i])
{
int j = e[i] ;
if(!st[j])
{
st[j] = true ;
if(match[j] == 0 || find(match[j]))
{
match[j] = x ;
return true ;
}
}
}
return false ;
}
int main()
{
scanf("%d%d%d",&n1,&n2,&m) ;
memset(h,-1,sizeof h) ;
while (m -- )
{
int a , b ; scanf("%d%d",&a,&b) ; add(a , b) ;
}
int res = 0 ;
for(int i = 1;i <= n1;i ++ )
{
memset(st,false,sizeof st) ; // 清空 , 表示右邊的點都還沒考慮過
if(find(i)) res ++ ;
}
printf("%d\n",res) ;
return 0 ;
}