<style> .reveal .slides { text-align: left; font-size:35px; } </style> # 圖論轉換與網路流建模 ---- - 最大獨立集 & 最大團 - 網路流建模 --- ## 最大獨立集 一張圖上，最多能選幾個點，使得選的點彼此都不沒有連邊  以上圖為例，選 3、4、7、8 四個點為一組解 ---- ## 最大團 一張圖上，最多可以選幾個點，使選的彼此之間都有連邊  以上圖為例，選 1、2、5、6 四個點為一組解 ---- 最大獨立集本身沒有好的做法，只能窮舉 subset 複雜度 $O(2^{N}M)$ 而最大團目前最佳複雜度為 $O(1.1888^n)$ 因此最大獨立集通常會轉換為用補圖做最大團 ---- ## 作法 獨立集 與 團 的概念完全相反 最大獨立集去建反圖之後，求最大團即可得到答案 <div style="position: absolute; right: 70vh; top: 38vh"> $\to$ </div> <div style="position: absolute; right: 70%;">  </div> <div style="position: absolute; right: 25%;">  </div> ---- 其中邊為雙向邊 ```cpp= [|6-11|12-13|42-58|] #define N 111 struct MaxClique{ // 0-base typedef bitset<N> Int; Int linkto[N] , v[N]; int n; void init(int _n){ n = _n; for(int i = 0 ; i < n ; i ++){ linkto[i].reset(); v[i].reset(); } } void addEdge(int a , int b) { v[a][b] = v[b][a] = 1; } int popcount(const Int& val) { return val.count(); } int lowbit(const Int& val) { return val._Find_first(); } int ans , stk[N]; int id[N] , di[N] , deg[N]; Int cans; void maxclique(int elem_num, Int candi){ if(elem_num > ans){ ans = elem_num; cans.reset(); for(int i = 0 ; i < elem_num ; i ++) cans[id[stk[i]]] = 1; } int potential = elem_num + popcount(candi); if(potential <= ans) return; int pivot = lowbit(candi); Int smaller_candi = candi & (~linkto[pivot]); while(smaller_candi.count() && potential > ans){ int next = lowbit(smaller_candi); candi[next] = !candi[next]; smaller_candi[next] = !smaller_candi[next]; potential --; if(next == pivot || (smaller_candi & linkto[next]).count()){ stk[elem_num] = next; maxclique(elem_num + 1, candi & linkto[next]); } } } int solve(){ for(int i = 0 ; i < n ; i ++){ id[i] = i; deg[i] = v[i].count(); } sort(id , id + n , [&](int id1, int id2){ return deg[id1] > deg[id2]; }); for(int i = 0 ; i < n ; i ++) di[id[i]] = i; for(int i = 0 ; i < n ; i ++) for(int j = 0 ; j < n ; j ++) if(v[i][j]) linkto[di[i]][di[j]] = 1; Int cand; cand.reset(); for(int i = 0 ; i < n ; i ++) cand[i] = 1; ans = 1; cans.reset(); cans[0] = 1; maxclique(0, cand); return ans; } }solver; ``` ---- ## 極大團 對於一張圖，選任意的點子集，如果不能在多選一個點使得選的點子集為更大的團  以上圖為例 {1, 4} 為一個極大團 {2, 3} 並非極大團，因為可以再多加點 6 變成更大的團 {1, 2, 3}, {2, 3, 6} {3, 5, 6} 也為極大團 ---- 程式碼每次跑到第 20 行時， bitset cans 中 值為 1 的節點代表有在窮舉的極大團裡 ```cpp= [|6-10|11-12|32-44|20|] #define N 80 struct MaxClique{ // 0-base typedef bitset<N> Int; Int lnk[N] , v[N]; int n; void init(int _n){ n = _n; for(int i = 0 ; i < n ; i ++){ lnk[i].reset(); v[i].reset(); } } void addEdge(int a , int b) { v[a][b] = v[b][a] = 1; } int ans , stk[N], id[N] , di[N] , deg[N]; Int cans; void dfs(int elem_num, Int candi, Int ex){ if(candi.none()&&ex.none()){ cans.reset(); for(int i = 0 ; i < elem_num ; i ++) cans[id[stk[i]]] = 1; ans = elem_num; // cans is a maximal clique return; } int pivot = (candi|ex)._Find_first(); Int smaller_candi = candi & (~lnk[pivot]); while(smaller_candi.count()){ int nxt = smaller_candi._Find_first(); candi[nxt] = smaller_candi[nxt] = 0; ex[nxt] = 1; stk[elem_num] = nxt; dfs(elem_num+1,candi&lnk[nxt],ex&lnk[nxt]); } } int solve(){ for(int i = 0 ; i < n ; i ++){ id[i] = i; deg[i] = v[i].count(); } sort(id , id + n , [&](int id1, int id2){ return deg[id1] > deg[id2]; }); for(int i = 0 ; i < n ; i ++) di[id[i]] = i; for(int i = 0 ; i < n ; i ++) for(int j = 0 ; j < n ; j ++) if(v[i][j]) lnk[di[i]][di[j]] = 1; ans = 1; cans.reset(); cans[0] = 1; dfs(0, Int(string(n,'1')), 0); return ans; } }solver; ``` --- ## 網路流建模 - 最小路徑覆蓋 - 最多不相交路徑 - 最大權閉合子圖 - 最大密度子圖 - 分層圖 flow - 平面圖最小割 --- ## 最小路徑覆蓋 給定一張有向無環圖 $(n \le 200, m \le 6000)$ 求出最少需要幾條路徑，可以使得每個點都剛好在一條路徑上  {1 $\to$ 5 $\to$ 4}, {6 $\to$ 7 $\to$ 8}, {2 $\to$ 3} ---- ## 作法 把每個點拆成 **入點** 和 **出點**，轉化為二分圖 原圖頂點數 減去 二分圖最大匹配數 即為最少路徑覆蓋數量 <div style="position:absolute; right: 70%;top:90%;">  </div> <div style="position: absolute; right: 55%;top:150%;"> $\to$ </div> <div style="position:absolute; right: 10%; top:90%;">  </div> ---- 匹配成功的點對 $(i, j)$，即為對於 $i$ 連到 $j$ 的邊接起來 <div style="position:absolute; right: 70%;top:90%;">  </div> <div style="position: absolute; right: 55%;top:150%;"> $\to$ </div> <div style="position:absolute; right: 10%; top:90%;">  </div> --- ## 最長遞增子序列 給出一段序列 $a$ $(n \le 500 )$，讓你求出： 1.最長遞增子序列的長度 2.最多同時可以取出幾個最長遞增子序列 3.如果第一個元素和最後一個元素可以用無數次，最長遞增子序列可以取出幾個 ---- ## 最長遞增子序列的長度 這個問題可以直接 DP 解 以第 $i$ 個為結尾的最長遞增子序列長度 $dp[i]$ ---- ## 最多同時可以取出幾個最長遞增子序列 ### 建模 <div style="font-size:28px;"> 確保每個點最多只能拿一次 先拆點，分成入點 $(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)$ </div> ---- ## 建模 ` a = [2, 4, 1, 3]` `dp = [1, 2, 1, 2]`  ---- ### 如果第一個元素和最後一個元素可以用無數次，最長遞增子序列可以取出幾個 想法：把點 1、點 N 分別當作第二個源點與第二個匯點 作法：把點 1 連到的邊與點 N 連出去的邊流量改為 INF 即可  --- ## 最大權閉合子圖 ---- ## 太空飛行計劃問題 <div style="font-size:30px;"> 有一個實驗集合 $E$ = { $E_1,E_2,...,E_m$ } 還有實驗儀器的集合 $I$ = { $I_1,I_2,...,I_n$ } $n,m \le 50$ 實驗 $E_j$ 需要用到的儀器是 $I$ 的子集 $R \in I$。 使用儀器 $I_k$ 的費用為 $c_k$ 元 實驗 $E_j$ 能獲得 $p_j$ 元 W 教授的任務是找出一個有效算法，確定在一次太空飛行中要進行哪些實驗並因此而配置哪些儀器才能使太空飛行的淨收益最大。 淨收益是指進行實驗所獲得的收入與配置儀器的費用的差額。 </div> ---- ## 建模 源點連到所有實驗，流量為得到的錢 $p_j$ 每個實驗儀器連到匯點，流量為使用費用 $c_i$ 每個實驗連到所有儀器，流量為 $\infty$ ---- ## 最小割 考慮割掉某個實驗，以下面為例 實驗 1 可以獲得 100 元 需要設備 A ( 成本 40 ) & 設備 B ( 成本 80 )  最小割出現割在實驗的地方 ( 實驗獲利 $\le$ 總成本 ) 實驗是收益，而收益不夠支出 因此 **不進行該實驗**。 ---- ## 最小割 考慮割掉某個設備，以下面為例 實驗 1 可以獲得 100 元 需要設備 A ( 成本 40 ) & 設備 B ( 成本 8 )  最小割出現割在設備的地方 ( 實驗獲利 > 總成本 ) 設備是花費，而支出少於收益 因此 **使用該儀器**。 ---- ## 轉換 <div style="font-size:30px;"> 我們得到的最小割集合為 { **不進行的實驗總收益**, **使用的儀器總成本** } 想得到最大收益為 **進行的實驗總收益** - **使用的儀器總成本** 要得到上面的東西為 全部實驗總收益 - 最小割 = ( **進行的實驗總收益** + **不進行的實驗總收益** ) - ( **不進行的實驗總收益** + **使用的儀器總成本** ) = **進行的實驗總收益** - **使用的儀器總成本** = 答案 在根據最小割 = 最大流，直接跑最大流即為答案。 </div> ---- ## 最大閉包(最大權閉合子圖) 給定一張有向圖，有點權且可正可負 要找到某個子圖，滿足以下： - 對於所有邊 $(u, v)$，若點 $v$ 在子圖中，則點 $u$ 也在子圖中 - 使得選的子圖點權總和最大 ---- ## 建模 源點連到所有正權點流量為點權 所有負權點連到匯點流量為點權(絕對值) 所有圖上的邊權重為 $\infty$ <div style="position:absolute; right: 60%;top:90%;">  </div> <div style="position:absolute; right: 50%;top:135%;"> $\to$ </div> <div style="position:absolute; right: 10%;top:90%;">  </div> 跑最大流即為答案，證明上面證過了 <!-- ## 最大密度子圖 給你一個長度為 $n$ $(n\le 100)$的序列 $T$，$S$ 為 $T$ 的任意子序列 inv(S)表示子序列 S 中的逆序對數數量 len(S) 表示S的長度，求出$\frac{inv(S)}{len(S)}$ 的最大值。 ## 題目轉換 (最大密度子圖) 給你一張圖 求某個子圖使得 $\frac{m}{n}$ 最大化 --> --- ## 分層圖 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 人 | 時間 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | --- | - | - | - | - | - | - | - | - | - | | A太空船位置 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | | B太空船位置 | 1 | 2 | -1 | 1 | 2 | -1 | 1 | 2 | -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$ 匯點從每天的月球連過去流量為無限大  ---- <div style="font-size:30px"> 對於建完的圖，我們可以二分搜總天數 $d$，建出 $d$ 天的分層圖 如果最大流流量為 $k$ 代表我們可以用 $d$ 天，把這 $k$ 個人運送到月球  </div> --- ## 平面圖最小割 結論：平面圖最小割 = 對偶圖最短路 平面圖為沒有邊相交的圖 ---- 例題：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 ---- 根據定理，平面圖最小割 = 對偶圖最短路  ---- 把每個平面當成一個點，而兩個點有連一條雙向邊為兩個平面用一條邊隔開 而兩個點之間的邊權即為隔開的那條邊的權重 而起始點從原本左下右上變成左上右下  ---- 好好地建邊 跑 dijkstra 即可把複雜度從 $O(MN^2)$ 變成 $O(MlgN)$  --- ### Question Time and Practice [Homework Link](https://vjudge.net/contest/533681) 提交期限到下下星期日 12/25 23:59 截止