<style> .reveal .slides { text-align: left; font-size:28px; } </style> # Flow and Matching ---- - Max Flow - Min-Cost Max-Flow - Min Cut - Bipartite Matching - Maximum Weight Perfect Bipartite Matching --- ## Max Flow ### 最大流 - 帶權有向圖 ($V,E$) - 邊權 $\ge$ 0 - 一個源點(source，簡稱s)，一個滙點(sink，簡稱t)，s, t$\in V$ - 求最大流量 ---- 最大流  想像有水流從源點，要流往滙點 源點有源源不絕的水流，邊上有流量限制，問最大流量是多少? 也可以想成是高速公路，邊權為每條公路當前車輛通過數量 有無限多台車要從S走到T，同時最多能有幾台車到達 ----  答案為 6 ---- ### [Dinic](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/flow/dinic_BCW.cpp) 時間複雜度: $O(V^2E)$ 常數很小，但通常不會跑到最差 #define SZ(x) (int)x.size() ### [ISAP](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/flow/isap.cpp) 時間複雜度: $O(V^3)$ 通常題目給的 $N$ 都很小 $N=50, 100, 300$ 之類 ---- ### 用法 1. flow.init(n, source, sink);//初始化幾個點,源點source滙點sink分別的編號 2. flow.add_edge(u, v, w);//加入一條點 u 連到點 v 流量限制為 w 的邊 3. flow.solve();//回傳值為最大流量 ---- ## 例題 [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，代表每個英雄可以殺一隻 接著每隻英雄連邊到可以擊殺的怪物流量限制為 1，每隻怪物可以被殺一次 ---- 先不考慮藥水的建圖，源點有源源不絕的流量 先建立源點，並且連到每個英雄節點流量限制為 1，代表每個英雄可以殺一隻 接著每隻英雄連邊到可以擊殺的怪物流量限制為 1，每隻怪物可以被殺一次  ---- 考慮藥水，每個英雄只能喝一瓶藥水 且有 K 瓶，我們可以建一個藥水的節點，從源點過去流量限制為 $K$ 在讓藥水的節點連到每個英雄流量限制為 1 (每個英雄只能喝一瓶)  ---- 最後整張圖就會變成，求出最大流量即為可以殺的怪物數量  ---- 設英雄節點為 0 ~ n-1 設怪物節點為 n ~ n+m-1  ---- ### 多源點多匯點 如果同時可能有很多個源點或很多個匯點 則可以分別建立超級源點與超級匯點  ---- ### 多源點多匯點 超級源點連到每個源點流量為無限 超級匯點連到每個匯點流量為無限  ---- ### 點有流量限制 如果題目有說每個節點只能流過流量 $k$ 則可以把點拆成兩個入點與出點，再連一條邊流量為 $k$ 下圖為例，假設節點2 有流量限制為 k，則左邊那之途 <div style="position: absolute; left: 7%; top:100%;">  </div> <div style="position: absolute; left: 30%; top:170%;"> $\to$ </div> <div style="position: absolute; left: 57%; top:100%;">  </div> --- ## Min Cut ### 最小割 對於一個網路流圖 $G = (V, E)$ 選一個集合的邊使得圖分成兩個子圖 $S$ 和 $T$，而源點在 $S$，匯點在$T$ 這個邊集合稱為割(cut) 最小割即為總流量最小的邊集合  ---- ### 最大流最小割定理 求出最小割即為求出最大流 ### 找出最小割集合 先跑一遍最大流，從源點 dfs，記錄所有走過的點 只要還有殘餘流量的邊就走， 走到的所有點即為源點那群， 沒走到的點即為匯點那群。 ---- 下圖為跑完 flow 後的剩餘流量圖， 從起點開始走，只走還有流量的邊 只會走到 S, 2 兩個點  因此跨兩個集合的邊為最小割 也就是(S, 1), (2, 5), (2, 4) 3 條邊 --- ## Min-Cost Max-Flow ### 最小費用流 最大流問題多一個費用參數 原本邊為 (u, v, w) 點 u 連到點 v 的邊最大流量為 w Min-Cost Flow (u, v, w, c) 點 u 連到點 v 的邊最大流量為 w，每用一單位的流量需要花費 c 塊錢 求滿足**最大流**的情況下的最小花費 ---- 限制: 不能有負環 時間複雜度: O($V^2E^2$) 不要亂砸都可以過 ---- ## 例題 給一張帶權有向圖，起點 $s$、終點 $t$ 求在每條邊只能用一次的情況下，最多可以構出幾條從起點到終點的路徑 且路經總和最小?  ----  答案為兩條路徑，最小總權重為 7+3 ---- ## 建圖 用 [min cost flow](https://github.com/jakao0907/CompetitiveProgrammingCodebook/blob/master/flow/MinCostFlow.cpp) 建圖 對於點 $u$ 連到點 $v$ 權重為 $w$ 的邊 轉成 flow 可以建成流量為 1 的邊 (每一條邊只能用一次) flow.addEdge($u, v, 1, w$); flow.solve() 會回傳 pair(maxFlow, minCost); --- ## Bipartite Matching ### 二分圖匹配 「二分圖」是一張無向圖。能把圖上的點分成兩群 ( $X$ 集合與 $Y$ 集合)。 而同一個集合裡面的點彼此不會有連邊， 邊只存在橫跨兩個集合 ( $X$ 與 $Y$ 之間 ) 二分圖匹配為挑選一些邊，每個點只能接觸最多一條邊  ---- ## 二分圖最大匹配 通常題目會求最大匹配數量，最小必定為 0 ### 例題 有很n隻地鼠以及很m個地鼠洞， 地鼠要在$s$秒內跑到洞裏面材行躲過老鷹的攻擊，然後地鼠跑的速度是$v$ 每個地鼠洞只能躲一隻地鼠，給你地鼠的位置跟地鼠洞的位置 問最少會有幾隻地鼠被攻擊? - n,m $\le$ 100 ---- 假設紅色點為地鼠，藍色點為地鼠洞 有連邊的為地鼠可以跑到的洞 可以發現地鼠只會跟地鼠洞連邊，並且求最大匹配數量 右圖為轉二分圖 <div style="position: absolute; left: 7%; top:100%;">  </div> <div style="position: absolute; left: 50%; top:170%;"> $\to$ </div> <div style="position: absolute; left: 65%; top:100%;">  </div> ---- 綠色為匹配成功的邊，最大匹配數量為 2  ---- ### 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$ 的數量級 --- ## Maximum Weight Perfect Bipartite Matching ### 二分圖最大權完美匹配 - 二分圖 - 完美匹配 - 每條邊有權重，求符合完美匹配下最大權重總和 - 簡稱 KM ( 使用 Kuhn–Munkres Algorithm ) ---- ## 例題 #### [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) 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 即為最小權完美二分圖匹配 ---- KM 複雜度為 $O(N^3)$ --- Flow, KM 等都是台灣站常出的模板題 如果是 Flow 題通常難點在於如何建邊 KM 則是要看出是模板題 :eyes: 今天講的只是入門而已， 更多的題目需要多看題目學習建圖以及轉換問題， 建議把 [網路流 24 題](https://loj.ac/p?tagIds=30) 好好做過一遍 ---- ### Question Time and Practice [Homework Link](https://vjudge.net/contest/499776) 提交期限到 6/30 23:59 截止