<style> .reveal .slides { text-align: left; font-size:32px; } </style> ## Special Graph & 0-1 BFS & 差分約束 #### 6/26 Advanced Competitive Programming ---- - 0-1 BFS - Special graph - Functional graph - Jellyfish graph - Cactus graph - 差分約束系統 --- ## 0-1 BFS 在權重只有 0 和 1 的圖上做 BFS ---- 在邊權只有 1 的情況下，可以用最一般的 BFS 計算最短路徑 $\rightarrow O(\vert E \vert )$ 但是在邊權只有 0 或 1 的情況下，可以用 0-1 BFS 來做，複雜度一樣為 $O(\vert E \vert )$ 可以降低 dijkstra 的複雜度 $O(E \log V)$ ---- ## 邊權只為 1 的 BFS 在一般的 BFS 的 queue 裡面 前面會有一段 dis 為 D 後面會有一段為D+1 ``` queue : [a...b ,c.....d] dis : [D...D ,D+1...D+1] ``` 每次會拿 queue 最前頭的點和 dis 繼續往新的點 BFS ， dis 更新成D+1，放到 queue 的最後面 ---- ## 0-1 BFS 當圖的邊權分成 0 或 1 ``` queue : [a...b ,c.....d] dis : [D...D ,D+1...D+1] ``` 要拿最前頭的點 dis = D 時，需要分成兩種情況 - 邊權為0 $\rightarrow$ 新的 dis 為 D - 邊權為1 $\rightarrow$ 新的 dis 為 D+1 由於使用的 STL 為 queue ， 遇到新的 dis 為 D 時，把新的 {點, dis} 塞到 queue 的最後面會出問題 ---- 因此可以考慮改用 deque ，把邊權為 0 的 {點, dis} 放到最前面 ``` D D+1 v v deque : [a...b ,c.....d ] dis : [D...D ,D+1...D+1] ``` ---- ```cpp= deque<int> que; que.push(s); while(!que.empty()){ int u = que.front(); que.pop(); if(vis[u]) continue; vis[u] = 1; for(int [v, w] : edge[u]){ if(dis[v] > dis[u] + w){ dis[v] = dis[u] + w; if(w == 1) que.push_back(v); else que.push_front(v); } } } ``` 每個邊只會跑過一次，時間複雜度：$O(\vert E \vert)$ ---- ### 例題：CodeChef - Chef and Reversing 給一張有向無權圖，求最少要翻轉幾條邊能從節點 1 走到節點 n  上圖答案為 2 ---- 對於一條有向邊 $(u, v)$ 分別建兩條邊 $(u, v, 0)$，走原本給的路 $(v, u, 1)$，翻轉該邊 然後跑最短路，最短路的成本即為翻轉的次數 ---- ### Atcoder - abc246E. Bishop 2 給一個 $n\times n$ 的西洋棋盤棋盤 有一些格子是障礙物，給你一隻主教在位置 $(s_x, s_y)$ 主教每次可以往對角線方向移動任意步 (不能穿越障礙物) 求移動到位置 $(e_x, e_y)$ 要幾次 $1\le n\le 1500$ ---- $s = (1, 3)$ $e = (3, 5)$ ``` ..I.X ....X ....X ....X ...X. .I.X. ...X. ...X. ..... -> ..... -> ..... -> ....I .X... .X... .X.I. .X... X.... X.... X.... X.... ``` $(1, 3)\to (2, 2)\to (4,4)\to (3, 5)$ 共3次 ---- 如果每次都暴力把四個方向可以走的位置都更新一遍， 那複雜度很明顯是爛的 $O(n^3)$ 想一下如何套 0-1 BFS 到這題上? ---- 分成兩種 case 1. 往其中一個方向走一單位，花費 1 2. 延續剛剛走的繼續走，花費 0 ``` ...... .1.1.. ..S... .1.1.. ...... ...... ``` ``` 0...0. .1.1.. ..S... .1.1.. 0...0. .....0 ``` ---- 即可轉變為 0-1 BFS ! 實作上的細節要分成四個方向記錄是否可以走 ---- ## Dial's algorithm 而如果所有的邊權重都 $\le k$， 也可以開 $k+1$ 個 queue 來分別維護從當前距離 $v$ 開始一直到距離 $v+k$ 的更新點 每當距離 $v$ 的 queue 空了就位移到下一個 queue，然後環狀的維護這些 queue 複雜度最差為 $O(nk)$ --- ## Functional Graph 一張圖，每個點各有剛好一條出去的邊(出度為1)  ---- ## Functional Graph 的特性 一張 Functional Graph 的連通子圖會由剛好一個環+一堆連向環的邊組成  圖中任意一個點一定有下一個點可以走，也被稱為 succesor graph ---- ## Functional Graph 經典例題 給一個Functional Graph，$Q$ 筆詢問 問點 $x$ 一直走 $k$ 步會到哪個點  succ(2,2)=4 succ(3,4)=4 ---- 當然可以直接 DFS 往下走 k 步，這樣會花 $O(k)$ 的時間，有點太爛了 所以我們考慮 $O(\log k)$ 的作法 ---- 考慮倍增法，一樣先建出每一個點往下走 $2^0,2^1,2^2,....,2^k$步會到哪裡 當要從 $x$ 點走 $k$ 時 會將 $k$ 二進制分解 走 $k=11$步 $\rightarrow$ 走 $8+2+1$ 步 ----  從 $2$ 開始走 $11$ 步 succ(2,11) =succ(succ(2,8),3) =succ(succ(succ(2,8),2),1) =succ(succ(4,2),1) =succ(3,1) =4 ---- 因此只要建出倍增表，是先處理每個點跳 $2^0,2^1,....2^k$ 會到哪個點 就可以在 $O(n \log n + q \log k)$ 解決這題 ---- ## Functional Graph 找環 可以從任意點DFS並紀錄每個點有沒有走過，如果走到了走過的點，代表有環 記錄走過+DFS，時間&空間複雜度 : $O(n)$ ---- 先看個[影片](https://www.youtube.com/watch?v=pKO9UjSeLew) ---- 剛剛的影片中要求時間複雜度 $O(n)$ ， 空間複雜度 $O(1)$ 顯然不能DFS 接下來介紹一下影片最後的作法是怎麼做的 ---- ## Floyd's Algorithm 在 Functional graph 判環的方法 可以用時間複雜度 $O(n)$ + 空間複雜度 $O(1)$ 解決 遇到題目限制 $n$ 很大 或是有限制空間複雜度就要用這個演算法 ---- 又稱龜兔賽跑演算法 放兩個指針，一快一慢放在圖上某個點慢慢走 這兩個指針一定會在環上某個點相遇 ---- 讓烏龜指針(慢指針)一次走一步 兔子指針(快指針)一次走兩步  ----  ----  ----  ----  ----  在環上會合了 但是這還不夠，有些題目可能還會問你「環的長度」或是「哪一個環上的點離 $x$ 最近」 ---- 這時我們想要知道哪一個環上的點離 $x$ 最近  ---- 作法會是把兔子指針移回點 $x$，烏龜指針留在原地 ，然後叫兔子指針走慢一點(一次一步) 根據某[數學證明](https://youtu.be/9YTjXqqJEFE?si=MldyHt3nnixfyKzZ)可以知道它們繼續走必定會在紅點會合  ---- 再來找環的長度，把烏龜指針放著，兔子指針慢慢繞一圈 記錄繞回烏龜走了幾步  以上做法都是 時間複雜度$O(n)$ + 空間複雜度$O(1)$ --- ## Jellyfish Graph 長得像水母的圖 由一個環和一些樹組成的圖 正好為無向的 Functional Graph  ###### 圖片取自《夜晚的水母不會游泳》好看 大推 ---- 常見的題型為在圖上做樹上DP 像是水母圖上最小點覆蓋，最大獨立集 ---- ### 淺談最小點覆蓋 最小點覆蓋：最小的點集使得圖上每條邊都至少與點集中一個點相鄰  圖中最小點覆蓋為4個點 ---- ### [ICPC 2020 台北站 F. Cable Protection](https://drive.google.com/file/d/1v6vk-VEtyNNDbTPOlc1JE_m9VllTHwi0/view) 給一張水母圖，求最小點覆蓋。  ---- 把環上延伸出去的樹去做樹上 DP 分兩種狀態 : 根節點被選 / 根結點沒被選 可以用BFS 每次取度數為 1 的葉節點從下往上更新 DP 值  ---- 接著就變成環上問題 留給大家想想:D --- ## Cactus graph 仙人掌圖，圖如其名，一球一球的   ---- ## 仙人掌圖的定義 仙人掌圖有很多可能的定義，根據題目給定 - 每條邊在恰好一個簡單環上 - 每條邊在最多一個簡單環上   ---- ## 經典問題 --- 判斷一張圖是否為仙人掌圖 判斷每條邊是否在恰好一個環上 ---- ### 作法 DFS，用 stack 維護當前遍歷的節點， 走到重複的節點就回退，把這個環上的點都記錄+1。 ( 環的起點不加，因為一個點可以在多個環上 ) 如果有節點被記錄超過 1 則此圖不是仙人掌圖。  <font color="#303030"><small>或者砸 SCC/BCC 模版在判斷每個環是否為簡單環</small></font> ---- ## ~~出題法則~~ ~~如果想把序列上的題目加難~~ $\to$ ~~就把他出在樹上~~ ~~如果想把樹上的題目加難~~ $\to$ ~~就把他改成仙人掌圖~~ --- ## 差分約束系統 ### Constraint Difference System 是求解關於一組不等式之方法。 $n$ 個變數和 $m$ 個約束條件組成 其中每個約束條件形如 ${ x_{j}-x_{i}\leq b_{k}(i,j\in [1,n],k\in [1,m])}$ 則稱其為差分約束系統。 ---- ## 例子 ${x_{1}-x_{2}\leq 8}$ ${x_{1}-x_{3}\leq 2}$ $\to x_{1}=3, x_{2}=-5, x_{3}=1$ ${x_{1}-x_{2}\leq 1}$ ${x_{1}-x_{3}\leq -1}$ ${x_{3}-x_{2}\leq 0}$ $\to$ 無解 <div style="position: absolute; right: 10%; top:0%;">  </div> <div style="position: absolute; right: 10%; top:80%;">  </div> ---- ## 作法 轉成圖論問題 對於所有 $x_{j}-x_{i}\leq k$ 連接一條邊 $(i, j)$，權重為 $k$ 最後再設置一個起點 $s$，連向所有邊邊權為 $0$ 從起點 $s$，跑 Bellman Ford/SPFA ， 若出現負環則代表這組不等式無解 ---- ## 建圖 ${x_{2}-x_{1}\leq 1}$ ${x_{1}-x_{3}\leq -1}$ ${x_{3}-x_{2}\leq 0}$  ---- ## 結果 跑完 Bellman Ford/SPFA 如果發現有負環，則此組不等式無解 否則所有點到起點的距離為其中一組解 ---- ## 變化 | 限制 | 建邊 | | -------- | -------- | | $x_{j}-x_{i}\leq k$ | addEdge($i, j, k$) | | $x_{j}-x_{i}\geq k$ | addEdge($j, i, -k$) | | $x_{j} = x_{i}$ | addEdge($i, j, 0$), addEdge($j, i, 0$) | ---- ## 區間問題轉換 給 $n$ 個區間 $[l_i, r_i]$ 以及 $c_i$ 要構造出一個序列 $\forall i\in [1, n]$ 滿足區間 $[l_i, r_i]$ 內的總和至少為 $c_i$， 構造出總和最小的序列。 ---- ## 轉換為前綴和處理 $[l_i, r_i]$ 至少為 $c_i$ 等價於前綴和 $pre_r$ - $pre_{l-1}$ 至少為 $c_i$ ---- 等價於前綴和 $pre_r - pre_{l-1}$ 至少為 $c_i$ $\to pre_r - pre_{l-1}\ge c_i$ 把序列上每個位置當成節點，即可轉換為差分約束問題 ! --- 題單連結 : [link](https://vjudge.net/contest/633968) 期限 : 7/24 20:00 要比賽ㄌ 大家暑假好好練><!!!!