<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)$ ---- ## 構圖方式 技巧 FLOW的題目難點就是如何建出一張合理且符合題目需求的圖 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/zkwflow.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 條邊 ---- 從源點出發，走所有還有剩餘流量的邊 所有走到的點(vis[x]==1)，即為最小割靠源點那側的子圖。 剩餘沒走到的點為最小割靠匯點那側的子圖 ```cpp= bool vis[MXN]; void dfs(int x){ vis[x] = 1; for(int i : flow.G[x]){ if(i.f > 0 && !vis[i.v]){ dfs(i.v); } } } dfs(source); ``` --- ## Bipartite Matching 二分圖匹配 * 二分圖最大匹配 * 二分圖最大權完美匹配 ---- 先給出二分圖的定義如下 : 二分圖的點可以分成兩個互斥的獨立集 $U$ 和 $V$ 的圖，使得所有邊都是連結一個 $U$ 中的點和一個 $V$ 中的點。頂點集 $U$、$V$ 被稱為是圖的兩個部分。 同一個集合裡的點互不連結  ---- 如何判斷一張圖是不是二分圖呢? 通常~~題目會講~~會使用著色法 : 也就是對圖跑DFS，使用DFS以兩個顏色著色，嘗試將任意相鄰兩點塗上不同顏色，如果發現有一點跟「相鄰且已經塗色的點」同一顏色，則二分圖不成立，反之成立 ---- 那如果題目沒講，也沒有給你圖，你就會需要自己知道他是不是二分圖，那就只能去思考是否為二分圖，以下給出一些是二分圖的例子 ---- 男女，棋盤(網格圖)，鬼腳圖，每個物品間的關係 等都有可能是二分圖，皆看題目的敘述 網格圖上的\*奇偶建圖 : 一張圖，$i$ 和 $j$ 分別是網格圖的座標，對於每一個格子點都對應一個 $(i+j)$ 的值，如果是奇數，那他就會被歸類到奇數點群，反之則是偶數點群。 會發現 $(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 ---- ### 複雜度 因為二分圖匹配的流量都是單位流量(流量為1)， dinic 跑在單位流量的圖上的複雜度為 $O(E\sqrt{V})$ 因此二分圖匹配使用 dinic 可以做到 $V,E \le 2 \cdot 10^5$ 的數量級 ---- ## [2020 TOPC G](https://drive.google.com/file/d/1IX0sJMs-HlpeTW4SHMVwjeEMX8MzhVd2/view) 給定一張 $n\times m$ 的圖，某些點不能種植:cactus: ，剩下的點可以，且限制你:cactus: 不能種植於相鄰的點。求最多可以種植多少 :cactus: $n*m \leq 10^5$ ---- 範例: ```txt 3 6 7 *.**.* *C**C* ...... C..C.C *.**.* *C**C* ``` ---- ```txt 3 6 *.**.* *1**2* ...... --> 345678 *.**.* *9**0* ``` 可以建出以下圖  ---- 那我們觀察畫出來的圖，以及原本的範例後，可以發現他是二分圖上最大獨立集。 那要怎麼求出二分圖上最大獨立集呢? 可以先從數量下手，由於二分圖的性質，你可以發現 (最大獨立集+最大匹配數=頂點數量) 所以可以使用匈牙利得到每張圖的答案。 (算出最大匹配數) 但這樣是不夠的，在此題需要輸出 :cactus: 的種植方法。 ----  因此我們可以發現，在此圖上的最大匹配的那些匹配邊，即為相連且只能選擇其中之一的邊，而其餘不再匹配上的點，則是可以全部選擇。 以此圖為例子，匹配邊即為 $(4-1),(6-5),(8-7)$ ---- 因此可以先把 $2,3,9,10$ 這些點選擇起來，而目前的圖看起來會像這樣  而至於匹配邊上的應該選擇誰呢，則是要看誰可以從起點(源點S)抵達，也就是阻斷整張圖。 ---- 所以根據上述的用法，就會聯想到需要使用最小割，而跑完最小割後的結果會變成以下:  (可以使得S到T永遠不連通。) 因此可以知道，4,5,7這三個點不能選。此題結束。 ---- 結論: 那在這張圖上，很明顯跑不到 flow 的 $n^3$ 複雜度，但因為他是一張奇偶建圖的二分圖，因此跑 dinic 的複雜度為7-6提到的 $O(E\sqrt{V})$ 就可以成功的跑最小割。 這題為思考後的結論題，但也用到許多flow的思考方式。 ---- ## [例題](https://lightoj.com/problem/knights-in-chessboard-ii) 題目大意：一個 $n\times 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~n (1-base)  ---- ## 匹配結果  二分圖左側每個點都匹配到右側的一個點 每個點恰好匹配到一次(完美匹配)， 總權重最大的完美匹配為 7+8=15 ---- ## 建圖實作 以此圖為例  1. graph.init(2); 完美匹配的兩側分別有幾個點(編號1~n) 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 即為最小權完美二分圖匹配 不過這樣有些原本是零的邊，則需要設為-INF 第二種做法是設定一個比所以權值都大的數字 (ex:INF) 然後在放入邊時放入(INF-value) 然後再用 $(邊數/2)*INF$ 減掉KM出來的答案，也即為最小值。 ---- ### Question Time and Practice [Homework Link](https://vjudge.net/contest/633979#overview)