Classic Flow Problems

• 二分圖
  • 最大獨立集
  • 最小點覆蓋
  • 最大權獨立集
• 最小路徑覆蓋
• 最多不相交路徑
• 最大權閉合子圖
• 分層圖 flow
• 平面圖最小割

二分圖最小點覆蓋（Minimum Vertex Cover）

König Theorem
最小點覆蓋：選出最少的點，滿足每條邊至少有一個端點被選。

二分圖中，最小點覆蓋 = 最大匹配。

二分圖最大獨立集 (Maximum Independent Set )

最大獨立集：選出最多的點，滿足兩兩之間沒有邊相連。

因為在最小點覆蓋中，任一條邊都被至少選了一個頂點，所以對於其點集的補集，任一條邊都被至多選了一個頂點，所以不存在邊連接兩個點集中的點，且該點集最大。

因此二分圖中，最大獨立集 = n - 最小點覆蓋。

No Prime Sum

給 \(n\) 個相異正整數，要刪除最少的整數，使得數字兩兩相加不能為質數

• \(2\le n\le 2000\)
• \(1\le a_i\le 10^5\)
  
  Image Not Showing Possible Reasons

  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted

  Learn More →

分 case 時間

• 奇數 + 奇數 = 偶數
• 偶數 + 偶數 = 偶數
• 奇數 + 偶數 = 奇數 (可能為質數)

由於所有數字都相異，因此相加若為偶數則 \(> 2\)

因此把所有可能相加為質數的 pair 連邊，會發現都是奇數和偶數連邊

形成一張二分圖，偶數一群，奇數一群
偶數和奇數之間有連邊

目標為相加不能為質數，也就是連邊的點對最多只能選一個留下來
\(\to\) 二分圖上最大獨立集。

求解

根據定理，最大獨立集 = n - 最小點覆蓋

跑二分圖最大匹配後，要找出要刪除哪些

使用 dinic 跑完後，從源點 \(S\) 開始跑殘餘流量圖 (code)

跟源點 \(S\) 同側的子圖有 2, 5, 11
和匯點 \(T\) 同側的子圖有 4, 7

而最大獨立集的點為左側(奇數)被走到和右側(偶數)沒被走到的點
也就是 5, 11, 4 即為其中一組最大獨立集

二分圖最大權獨立集 (Maximum Weighted Independent Set )

方格取數問題

有一個 \(m\times n\) \((1\le n, m\le 30)\) 格的棋盤，每格中都有一個正整數。
要從方格中取數，使得取的數字皆沒有共邊，且取出的數的總和最大。

選 (0, 1), (1, 0), (1, 2), (2, 1)
2+3+3+3=11

方格上取的數字皆沒有共邊 \(\to\) 二分圖獨立集 (奇偶分群)
取出的數的總和最大 \(\to\) 最大權

\(\to\) 二分圖帶權最大獨立集

嘗試把二分圖畫出來

把相鄰的格子連邊流量設 INF
起點連到奇點，權重為奇點上的權重
偶點連到匯點，權重為奇點上的權重

目標 –- 選的點不能相鄰

要使得選的點皆不相鄰，等價於至少有一個到源點或匯點的邊要割掉。
（割中間流量為無窮大的邊，因此不選）

要選權重總和最少的邊集合割掉，使得源點與匯點不連通
\(\to\) 最小割

根據定理 最小割 = 最大流

因此把全部點的總和 減去 建出來的圖的最大流即為答案

最小路徑覆蓋 (Minimum Path Cover)

給定一張有向無環圖 \((n \le 200, m \le 6000)\)
求出最少需要幾條路徑，可以使得每個點都剛好在一條路徑上

{1 \(\to\) 5 \(\to\) 4}, {6 \(\to\) 7 \(\to\) 8}, {2 \(\to\) 3}

作法

把每個點拆成 入點 和 出點，轉化為二分圖
原圖頂點數 減去 二分圖最大匹配數 即為最少路徑覆蓋數量

匹配成功的點對 \((i, j)\)，即為對於 \(i\) 連到 \(j\) 的邊接起來

最長遞增子序列

給出一段序列 \(a\) \((n \le 500 )\)，讓你求出：

1.最長遞增子序列的長度

2.最多同時可以取出幾個最長遞增子序列

3.如果第一個元素和最後一個元素可以用無數次，最長遞增子序列可以取出幾個

最長遞增子序列的長度

這個問題可以直接 DP 解

以第 \(i\) 個為結尾的最長遞增子序列長度 \(dp[i]\)

最多同時可以取出幾個 LIS

建模

確保每個點最多只能拿一次
先拆點，分成入點 \((i)\) 與出點 \((i')\)，入點連到出點流量為 \(1\)

源點連到所有 \(i \in\) (dp[i] = 1)，addEdge\((S, i, 1)\)

對於所有 \(i \in\)(dp[i] = 最長長度)的連到匯點，addEdge\((i', T, 1)\)

對於所有 \((i, j)\) 符合\(a[i]<a[j] \wedge dp[i]+1=dp[j]\) 建邊
點 \(i\) 的出點連出去到 點 \(j\) 的入點，addEdge\((i', j, 1)\)

建模

a = [2, 4, 1, 3]

dp = [1, 2, 1, 2]

如果第一個元素和最後一個元素可以用無數次，最長遞增子序列可以取出幾個

想法：把點 1、點 N 分別當作第二個源點與第二個匯點

作法：把點 1 連到的邊與點 N 連出去的邊流量改為 INF 即可

最大權閉合子圖

Maximum Closure Problem

太空飛行計劃問題

建模

源點連到所有實驗，流量為得到的錢 \(p_j\)
每個實驗儀器連到匯點，流量為使用費用 \(c_i\)
每個實驗連到所有儀器，流量為 \(\infty\)

最小割

考慮割掉某個實驗，以下面為例

實驗 1 可以獲得 100 元
需要設備 A ( 成本 40 ) & 設備 B ( 成本 80 )

最小割出現割在實驗的地方 ( 實驗獲利 \(\le\) 總成本 )
實驗是收益，而收益不夠支出
因此 不進行該實驗。

最小割

考慮割掉某個設備，以下面為例

實驗 1 可以獲得 100 元
需要設備 A ( 成本 40 ) & 設備 B ( 成本 8 )

最小割出現割在設備的地方 ( 實驗獲利 > 總成本 )
設備是花費，而支出少於收益
因此 使用該儀器。

轉換

最大閉包(最大權閉合子圖)

給定一張有向圖，有點權且可正可負

要找到某個子圖，滿足以下：

• 對於所有邊 \((u, v)\)，若點 \(v\) 在子圖中，則點 \(u\) 也在子圖中
• 使得選的子圖點權總和最大

建模

源點連到所有正權點流量為點權
所有負權點連到匯點流量為點權(絕對值)
所有圖上的邊權重為 \(\infty\)

建出來的圖即可轉換為上一題同一個問題

分層圖 flow

星際轉移問題

有 \(k\) \((1 \le k \le 50)\)個人要從地球到月球， 其中有 \(n\) \((1\le n \le 13)\) 個太空站，
每個太空站可以容納無限多的人

有 \(m\) \((1 \le m \le 20)\)個太空船在一些太空站之間週期性的來回
每個太空船可以容納 \(h_i\) 個人
並且從當前太空站到下一個所需時間為 1 秒

問你是否能把所有人送到月球，或者輸出無解

有 1 人要載
A 太空船可以載 1 人, B 太空船可以載 1 人

所需時間為 5

網路流? 但好像沒辦法建圖?

觀察測資大小

• \(k\) \((1 \le k \le 50)\) 個人
• \(n\) \((1\le n \le 13)\) 個太空站
• \(m\) \((1 \le m \le 20)\)個太空船

會發現最差的情況下只需要最多 \(n^2\cdot k\) 天把所有人載完

對於所有太空站在所有時間點都變成一個節點
把圖建成以下

對於每個太空船每天在的位置建邊到下一天的位置流量為 \(H_i\)

每個人也可以第 \(d\) 天待在同一個太空站待到第 \(d+1\) 天
流量為無限大 (太空站可以容納無限多個人)

並且把 flow 的
源點連到地球的第 0 天的節點流量為總人數 \(k\)
匯點從每天的月球連過去流量為無限大

平面圖最小割 (Min Cut in a Planar Graph)

結論：平面圖最小割 = 對偶圖最短路

平面圖為沒有邊相交的圖

例題：BZOJ1001 –- 狼抓兔子

給一張 \(N\times M\) \((1\le N, M\le 1000)\) 的網格圖
一開始有無限多隻兔子在左下角 (1, 1)，而有野狼要抓他們
所以要跑到右上角 \((N, M)\) 的位置

而每次可以從 (i, j) 跑到 (i+1, j), (i, j+1), (i+1, j+1) 的位置
並且每條道路有流量上限，想問你在不超過上限的情況下最多有幾隻兔子可以到右上角

給一張 \(N\times M\) \((1\le N, M\le 1000)\) 的網格圖
一開始有無限多隻兔子在左下角 (1, 1)，而有野狼要抓他們
要跑到右上角 \((N, M)\) 的位置

\(N\times M\) \((1\le N, M\le 1000)\)

很明顯這題是一個平面圖上的最大流問題，
但 \(N\times M\) 最大會到 1e6 直接跑 flow 會 TLE

平面圖

平面圖是可以畫在平面上並且使得不同的邊可以互不交疊的圖

平面圖的對偶圖

對於平面圖 G 的對偶圖 G*，其 G 的每個面皆為對偶圖 G* 的點，
G 中的每條邊 e ，為 G* 連接兩個面的邊 e*
而如果 G* 中一條邊 e* 連接的為同一個平面，則此條邊為自環

根據定理，平面圖最小割 = 對偶圖最短路

把每個平面當成一個點，而兩個點有連一條雙向邊為兩個平面用一條邊隔開
而兩個點之間的邊權即為隔開的那條邊的權重

而起始點從原本左下右上變成左上右下

好好地建邊
跑 dijkstra 即可把複雜度從 \(O(MN^2)\) 變成 \(O(M\log N)\)

Flow 的建模跟 DP 想轉移式一樣，多看多練習就能熟悉

而如果你是隊上負責建模的應該要去好好刷以下題單

網路流 24 題

大部分的網路流的問題都是經典問題的轉換
好好寫完就能成為 flow 的神了 m(_ _)m

Question Time and Practice

Homework Link