<style> .reveal .slides { text-align: left; font-size:35px } </style> ## 匹配與網路流 ---- * Flow * Match * KM --- ## Flow 1. Max Flow 2. Min-Cost Max-Flow 3. Min Cut --- ## Max Flow 最大流 在一張邊權 $\ge 0$ 的有向圖上求出從源點 (source) 到匯點 (sink) 的最大流量 範例圖片:求從1到6的最大流量 1即為源點 6即為匯點  1即為源點 而6即為匯點 ---- 而最大流顧名思義就是要讓圖上的流量最大化，而根據這張圖，考慮1(源點)有無限流量，那最終可以流到6(匯點)的值即為答案。  而這張圖上的這個問題答案為14。 ---- ## [增廣路](https://blog.csdn.net/Fine_rose/article/details/77170272) 那要如何解決這個問題呢，就會需要用到增廣路，增廣路具體上的想法就是加上反邊就可以舉出最優解。 可以透過不斷嘗試(嘗試提出增廣路)然後再去尋找是否有更多選擇可以抵達匯點。重複此操作。 到最後沒有路徑可以抵達匯點的時候即為解答。 ---- ## 兩種算法 Dinic VS ISAP ### [Dinic模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/flow/dinic_BCW.cpp) 時間複雜度: $O(V^2E)$ 常數很小，但通常不會跑到最差 #define SZ(x) (int)x.size() #define PB push_back ### [ISAP模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/flow/isap.cpp) 時間複雜度: $O(V^3)$ ~~ISAP教派都號稱是線性~~ 通常題目給的 $N$ 都很小 $N=50, 100, 300$ 之類 *V=vertices=頂點數量 *E=edges=邊數量 ---- ### 用法 1. flow.init(n, source, sink);//初始化幾個點,源點source滙點sink分別的編號 2. flow.add_edge(u, v, w);//加入一條點 u 連到點 v 流量限制為 w 的邊 3. flow.solve();//回傳值為最大流量 ---- ## dinic想法 1. BFS : 在做增廣路徑前先針對距離 $s$ (源點) 的每一層做BFS，確保流量在經過每一層的節點後一定會向下流到下一層，也就是對圖做成分層圖(層次圖)。 2. DFS : 用DFS找出圖的增廣流(也就是做增廣路直到找不出任何一條) ---- ## dinic時間複雜度分析 裡面使用了較為複雜的概念 : [當前弧優化](https://blog.csdn.net/Floatiy/article/details/80961870) 因此不須太過注意，只需要注意到，顯然的，層次圖的層次是不會超過 $N$ 層，而DFS做一次增廣的時間複雜度為 $O(V\cdot E)$ 因此總複雜度為 $O(V^2\cdot E)$ ---- ## ISAP 會發現 dinic 裡面每次都是交錯BFS與DFS，會發現做完分層圖，跑完增廣後又需要再跑一次分層圖，非常浪費時間，因此ISAP的主要想法就是把兩個過程結合再一起，反向做分層圖然後在做出增廣的同時分層，就只需要做到一次就好。 而這樣改的結果則是對每個頂點進行分層的處理所以會壓掉對邊的複雜度，只留下對點的複雜度 因此複雜度變成 $O(V^3)$ ---- ## 構圖方式 1. 多源點改單源點 2. 多匯點改單匯點 3. 點容量改邊容量 4. 多重邊改單邊 5. 無向圖改有向圖 6. 雙向圖等量減少/增加 ---- ## 例題 [TIOJ 2134. 魔法藥水](https://tioj.ck.tp.edu.tw/problems/2134) 有 $N$ 個英雄和 $M$ 隻怪物，英雄們要消滅怪物，每個英雄只能消滅特定的一些怪物裡的其中一隻。有 $K$ 瓶藥水，一罐藥水可以使一個英雄多消滅一隻怪物，一個英雄最多只能服用一瓶藥水 最多可以消滅多少隻怪物。 $N, M, K \le 500$ ---- ## sample input 1 3 個英雄 5隻怪物 2瓶藥水 第一個人可以殺掉第 1, 2, 3, 5 隻怪物 第二個人可以殺掉第 2, 5 隻怪物 第三個人可以殺掉第 1, 2 隻怪物 ## sample output 1 4 第一個英雄喝一罐藥水殺掉第 3, 5 隻怪物 第二個英雄殺掉第 2 隻怪物 第三個英雄殺掉第 1 隻怪物 ---- ## 建圖 分成兩部分 $N$ 個英雄與 $K$ 個藥水 每個英雄只能特定的一些怪物裡的殺一隻 且每個英雄只能喝最多一瓶藥水 會發現這就是多源點多匯點的構圖 1. 先建立唯一源點 2. 並且連到每個英雄節點流量限制為 $1$，代表每個英雄可以殺一隻 3. 接著每隻英雄連邊到可以擊殺的怪物流量限制為 $1$，代表是他殺的怪物 4. 最後把怪物的點連接到唯一匯點，流量為 $1$，代表每隻怪物可以被殺一次 ---- 先不考慮藥水的建圖，源點有源源不絕的流量  ---- 考慮藥水，每個英雄只能喝一瓶藥水 且有 K 瓶，我們可以建一個藥水的節點，從源點過去流量限制為 $K$ 在讓藥水的節點連到每個英雄流量限制為 1 (每個英雄只能喝一瓶)  ---- 最後整張圖就會變成，求出最大流量即為可以殺的怪物數量  ---- 設英雄節點為 0 ~ n-1 設怪物節點為 n ~ n+m-1  --- ## Min-Cost Max-Flow 最小花費最大流 [模板](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/flow/MinCostFlow.cpp) 其實也是max flow的延伸問題，在原本的max flow上只有三個參數 $(u,v,w)$ 意義為從 $u$可以到 $v$的流量為 $w$，而在 Min-Cost Max-Flow上則多一個參數，$(u,v,w,c)$，意義為從 $u$可以到 $v$的流量為 $w$，而其中每一單位的流量需要花費 $c$元 需要在滿足最大流量上的情況最小化花費 ---- ## 用法 對於點 $u$ 連到點 $v$ 權重為 $w$ 的邊 轉成 flow 可以建成流量為 1 的邊 (每一條邊只能用一次) flow.addEdge($u, v, 1, w$); flow.solve() 會回傳 pair(maxFlow, minCost); ---- 限制: 不能有負環 時間複雜度: O($V^2E^2$) 是在網路流的基礎上做最短路  ---- 而其實上面最短路的實現是可以有以下這些方式，但不會卡，因此使用模板的就好，不要亂砸都會過 | 演算法 | 特點 | 缺點 | | ---- | ---- | ---- | | bellman-ford | 可以解決負權值，但不能解決負環 | 多次鬆弛，複雜度常數大 | | SPFA | 經過優化的BF，在稀疏圖上高效 | 由於使用多個array進行優化，需維護的東西較多，因此速度最慢 | | Dijkstra\*改良版 | 速度最快 | 無法直接處理負權值邊 | [詳情可以參考](https://blog.csdn.net/lym940928/article/details/90209172) --- ## Min Cut 最小割 對於一張網路流的圖，選出一個集合的邊把圖割開變成兩張子圖(S和T需分開)，其中的這個集合則為"割" 而最小割則為總流量最小的集合  ---- 也就是說，要求出最小割就需要先求出最大流，那要做的第一件事情就是先跑一次最大流 跑完最大流後，代表已經求不出更多增廣路徑(不會有從S可以走到T的任何一條路) 然後你就會獲得一張只剩下殘餘流量的圖 ---- 接下來就是從源點開始DFS，記錄全部走過的點 只要還有剩餘流量的邊全部都要走 走到的點即為源點那半邊的子圖 沒走到的點即為匯點那半邊的子圖 ---- 給出範例(剩餘流量圖)  只需要在上面DFS，有邊就走即可。 也就是說跨兩個集合的邊為最小割 也就是(S, 1), (2, 5), (2, 4) 3 條邊 --- ## Bipartite Matching 二分圖匹配 * 二分圖最大匹配 * 二分圖最大權完美匹配 ---- 先給出二分圖的定義如下 : 二分圖的點可以分成兩個互斥的獨立集 $U$ 和 $V$ 的圖，使得所有邊都是連結一個 $U$ 中的點和一個 $V$ 中的點。頂點集 $U$、$V$ 被稱為是圖的兩個部分。 同一個集合裡的點互不連結  ---- 如何判斷一張圖是不是二分圖呢? 通常~~題目會講~~會使用著色法 : 也就是對圖跑DFS，使用DFS以兩個顏色著色，嘗試將任意相鄰兩點塗上不同顏色，如果發現有一點跟「相鄰且已經塗色的點」同一顏色，則二分圖不成立，反之成立 ---- 那如果題目沒講，也沒有給你圖，你就會需要自己知道他是不是二分圖，那就只能去思考是否為二分圖，以下給出一些是二分圖的例子 ---- 男女，棋盤(網格圖)，鬼腳圖，每個物品間的關係 等都有可能是二分圖，皆看題目的敘述 網格圖上的\*奇偶建圖 : 一張圖， $i$ 和 $j$ 分別是網格圖的座標，對於每一個格子點都對應一個 $i+j$ 的值，如果是奇數，那他就會被歸類到奇數點群，反之則是偶數點群，於是就符合了二分圖的性質 於是就奇偶建圖就是一個在二分圖問題上常見的建圖方法。(但其實也一樣可以適用著色法去跑一次) ---- 二分圖匹配則是挑選某些邊，使每個點最多只接觸一條邊 那你會發現，最小一定是 $0$ 啥都不選 :x: 同時，二分圖匹配也可以轉換成最大流的模型去做，其中一邊的點群皆連接到源點，而另外一邊的點群皆連接到匯點，那就可以無痛轉換成最大流，而其中權重皆為1  ---- 而要求出匹配的節點為哪幾對可以在 add_edge(u, v, 1) 時， 紀錄當前邊在 flow.edge[u] 的 index ， ```cpp index[u].push_back(v,E[u].size()); ``` 跑完 flow 之後 去看 flow.edge[u][index] 的剩餘流量， 如果有流過去代表有配對到，此邊剩餘流量會為 0 ```cpp flow.E[i][j.second].f==0 ``` --- ## 二分圖最大匹配 ### 匈牙利演算法 討論到這個演算法就會先提到交替路徑和增廣路徑 交替路徑就是選擇一個點當作起點，沿著 **未匹配/匹配** 的邊交替走 增廣路徑就是選擇一個未匹配的點出發，走交替路徑，如果路上遇到另外一個未匹配的路徑，則這條交替路徑即為增廣路徑(兩端皆未匹配) 而增廣路徑的重點為 : 未匹配邊==匹配邊+1 ，因此只要把增廣路徑中未匹配邊和匹配邊互換，則一定會比原本的匹配方式好，而最大匹配就是圖中完全沒有增廣路徑。 ----  ---- 模板 ```cpp= bool dfs(int u){ for(int i=1;i<=n;i++){ if(Map[u][i]&&!vis[i]){ //有連通且未拜訪 vis[i]=1; //紀錄是否走過 if(S[i]==-1||dfs(S[i])){ //紀錄匹配 S[i]=u; return true; //反轉匹配邊以及未匹配邊的狀態 } } } return false; } // 記得每次使用需清空vis數組 // 其中Map為鄰接表 S為紀錄這個點與誰匹配 ``` ```cpp= for(int i=1;i<=p;i++){ memset(vis,0,sizeof(vis)); if(dfs(i)) ans++; } ``` ---- ### Maximum Matching using Maximum Flow 二分圖問題可以轉成最大流去做 建立源點匯點， 源點連到二分圖集合 $X$ 的所有點權重為 1 二分圖集合 $Y$ 的所有點連到匯點權重為 1 (每個點只能被匹配到一個) 求出最大流即為最大匹配數量 ---- 而要求出匹配的節點為哪幾對可以在 add_edge(u, v, 1) 時， 紀錄當前邊在 flow.edge[u] 的 index ，跑完 flow 之後 去看 flow.edge[u][index] 的剩餘流量， 一開始為 1，如果有流過去代表有配對到，此邊剩餘流量會為 0 ---- ### 複雜度 因為二分圖的特殊性， flow 跑在二分圖上的複雜度為 $O(E\sqrt{V})$ 因此可以做到 $V,E \le 2 \cdot 10^5$ 的數量級 ---- ## [例題](https://lightoj.com/problem/knights-in-chessboard-ii) 題目大意：一個 $n*m$ 的棋盤上放棋子。然後有 $k$ 個棋子是不能放的。放了一個棋子後，它周圍馬步八格地方就不能放了(如圖所示)，問最多放多少個棋子。  ---- 先得出他的差值 ```cpp int dx[]={-2,-2,-1,-1,2,1,2,1}; int dy[]={-1,1,-2,2,-1,-2,1,2}; ``` 然後會發現可以奇偶建圖，因為他就是一張天然的網格圖，然後就可以把不能相鄰放置的棋子參與匹配，丟進去二分最大匹配模板即可獲得答案。 ---- 具體怎麼建圖 ```cpp for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(map[i][j]!=-1&&(i+j)&1){ for(int k=0;k<8;k++){ int nx=i+dx[k],ny=j+dy[k]; if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&map[nx][ny]!=-1) add(map[i][j],map[nx][ny]); } } } } ``` ---- ## [例題2](https://www.luogu.com.cn/problem/P2756) 題目大意 : 就是給你 $n$ 和 $m$ ，跟你說 $1,2,3...n$ 是一個點群， $n+1,n+2,n+3...m$則是另外一個點群，再給你兩個點群間的關係，詢問最大匹配數以及匹配方法。 ---- ### 解法1 : 最大流+DFS殘流量圖 那很明顯題目給出了兩個點群，所以只需要把圖簡單的建好(源點連到 $1$ ~ $n$ ， 匯點從 $n+1$ ~ $m$ 連過去)然後跑一次最大流後，只需要枚舉每條邊是否有流量即可(為0的話代表有跑到這條邊，這條邊是一個正確的匹配) ### 解法2 : 匈牙利演算法 使用匈牙利演算法自帶的匹配機制，在最後把有成功配對的點輸出即可 ```cpp for(ll i=n+1;i<=m;i++){ if(S[i]) cout<<S[i]<<" "<<i<<"\n"; } ``` --- ## 二分圖最大權完美匹配 簡稱 KM ( 使用 Kuhn–Munkres Algorithm ) 他是在完美匹配的基礎下(每個點都有匹配點) 且每條邊都有權重 求出最大權重的總和 複雜度為 $O(N^3)$ 但通常不會跑滿，因此題目的 N 會出到 1000 就 模板 對 ---- ## 例題 #### [NCPC2020 決賽 problem J. Robot Dispatch Problem](https://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=56342) 給你一個 $N \times N$ $(N \le 50)$的矩陣 每格有一個數字 $a_{ij}$， 求每列每行都選一個數字的情況下總和最大 <div style="position: absolute; left: 35%; top:100%;">  </div> <div style="position: absolute; left: 10%; top:100%;">  </div> ---- 為什麼這題可以使用 KM 呢，首先會發現它可以變成二分圖，然後把每一個列要剛好配對到一個行，且不同重複配對到 因此可以將行列分別轉成節點，第 $i$ 列第 $j$ 行 連邊權重為 $a_{ij}$ ---- ### 模板 ```cpp= [|5-8|9|40-48|] struct KM{ // max weight, for min negate the weights int n, mx[MXN], my[MXN], pa[MXN]; ll g[MXN][MXN], lx[MXN], ly[MXN], sy[MXN]; bool vx[MXN], vy[MXN]; void init(int _n) { // 1-based, N個節點 n = _n; for(int i=1; i<=n; i++) fill(g[i], g[i]+n+1, 0); } void addEdge(int x, int y, ll w) {g[x][y] = w;} //左邊的集合節點x連邊右邊集合節點y權重為w void augment(int y) { for(int x, z; y; y = z) x=pa[y], z=mx[x], my[y]=x, mx[x]=y; } void bfs(int st) { for(int i=1; i<=n; ++i) sy[i]=INF, vx[i]=vy[i]=0; queue<int> q; q.push(st); for(;;) { while(q.size()) { int x=q.front(); q.pop(); vx[x]=1; for(int y=1; y<=n; ++y) if(!vy[y]){ ll t = lx[x]+ly[y]-g[x][y]; if(t==0){ pa[y]=x; if(!my[y]){augment(y);return;} vy[y]=1, q.push(my[y]); }else if(sy[y]>t) pa[y]=x,sy[y]=t; } } ll cut = INF; for(int y=1; y<=n; ++y) if(!vy[y]&&cut>sy[y]) cut=sy[y]; for(int j=1; j<=n; ++j){ if(vx[j]) lx[j] -= cut; if(vy[j]) ly[j] += cut; else sy[j] -= cut; } for(int y=1; y<=n; ++y) if(!vy[y]&&sy[y]==0){ if(!my[y]){augment(y);return;} vy[y]=1, q.push(my[y]); } } } ll solve(){ // 回傳值為完美匹配下的最大總權重 fill(mx, mx+n+1, 0); fill(my, my+n+1, 0); fill(ly, ly+n+1, 0); fill(lx, lx+n+1, -INF); for(int x=1; x<=n; ++x) for(int y=1; y<=n; ++y) // 1-base lx[x] = max(lx[x], g[x][y]); for(int x=1; x<=n; ++x) bfs(x); ll ans = 0; for(int y=1; y<=n; ++y) ans += g[my[y]][y]; return ans; } }graph; ``` ---- ## 建圖 以此圖為例  1. graph.init(2); 2. graph.addEdge(1, 1, 3); 第一列連到第一行權重為 3 graph.addEdge(1, 2, 7); 第一列連到第二行權重為 7 graph.addEdge(2, 1, 8); 第二列連到第一行權重為 8 graph.addEdge(2, 2, 9); 第二列連到第二行權重為 9 3. graph.solve(); 回傳 15 為最大總權重 ---- ### 最小權完美二分圖匹配 那最小權應該怎麼做呢? KM 反過來? 作法為把每個邊權乘上 -1 後直接跑 KM 再把得到的總權重乘上 -1 即為最小權完美二分圖匹配 就這 --- ## 副教練的話 Flow, KM 等都是台灣站常出的模板題 (幾乎每年都至少一題) 如果是 Flow 題通常難點在於如何建邊 KM 則是要看出是模板題 :eyes: 今天講的只是入門而已， 更多的題目需要多看題目學習建圖以及轉換問題， 建議把 [網路流 24 題](https://loj.ac/p?tagIds=30) 好好做過一遍 ~~只要把網路流24題刷完就不會有其他網路流的題目困住你了~~ ---- ### Question Time and Practice [Homework Link](https://vjudge.net/contest/566699)