2020 競技程設教材 HackMD Book

2019 Week 11: Graph

本主題會用到第四週教材的圖與樹的術語

術語不熟的話，底下介紹的都看不懂了

圖論最為重要觀念就是 "連通"，
若說此圖為連通圖，則所有點能透過邊接到任一點 (弱連通)^[1]。
而不只接上還能走過去^[2]，則為強連通。

例如：

上圖弱連通但非強連通。

若是這樣：

則上圖為強連通。

點與邊的表示方式

以下兩個結構體，將成為本篇的慣例

• 點

struct node {
  int id, w; // id := 點編號, w := 連結到此點的權重 (邊權重)
  bool operator<(const node &rhs) const {
    return w > rhs.w; // 使 priority_queue 為 min heap
  }
};

• 邊

struct edge {
  int u, v, w; // u := 起端編號, v := 終端編號, w := 權重
  bool operator<(const edge &rhs) const {
    return w > rhs.w; // 使 priority_queue 為 min heap
  }
};

討論圖的邊，常會有

$u$ 是邊起點與

$v$ 是邊終點的慣例用符

Minimum spanning tree (MST)

最小生成樹 (Minimum spanning tree) 簡稱 MST。

給定圖

$G=(E,V)$，使用

$E$ 子集連結所有點 (來自

$V$) 所得到的樹為生成樹。

$E$ 為邊集合，

$V$ 為點集合

若帶權重圖的某生成樹為所有生成樹中權重總和最小，則稱此為最小生成樹

^[3]

給定一個連通圖，找出一個最小生成樹

Kruskal 演算法

Kruskal 用了兩個重要的觀念：

• 樹是無環的連通圖
• 若圖中只有點沒有任何邊，那麼每個點都是一個獨立的連通塊。

這有什麼可利用的呢？

若將一點連向另一點，整張圖就少了一個連通塊，
反覆操作，最終圖上只會有一個連通塊，若最終連通塊沒有環，那他就是樹，他就是此圖的生成樹。

於是在連通塊與連通塊相連這個動作，確保產生的連通塊無環就行：
連通塊

$A$ 想與連通塊

$B$ 相連，只要

$A\ne B$，那麼相連的新連通塊保證無環。

怎樣產生出最小生成樹？

所以若在

$A$ 與

$B$ 相連時每次考慮最小權重的邊，那最終產生的一定是最小權重的生成樹

沒錯哦，這是最優子結構

^[4]

實作上先將每個邊依照權重排序，

vector<edge> E;
  :
  .
sort(E.begin(), E.end(), [&](edge x, edge y) { return x.w < y.w; });

接著用 DFS 判斷塊與塊是否為同個連通塊，若不是的話就能相連起來。
DFS 每次都將連通塊的邊遍歷，複雜度為

$O(|E{|}^2)$

還記得 Union-Find Forest 嗎？分類問題包括連通塊的分類也能使用它：

for (auto e: E) {
  int a = Find(e.u), b = Find(e.v);
  if (a != b) {
    Union(e.u, e.v);
    cost += e.w;
    MST.push_back({u, v, w});
  }
}

複雜度約為

$O(|E|\log |E|+|E|\cdot \alpha )$
其中

$\alpha =\alpha (|E|)$ 為 Union-Find Forest 的時間成本 (通常很小)

範例 UVa OJ 10369 Arctic Network：

很直覺的，使 outpost 都能通訊的簡單方法，就是做出樹
畢竟若兩點已能通訊，加入一條形成環的邊不會更好。

而想使 D 下降的方法就是將 network 上的 distance 盡量小，也就是要求最小生成樹
而生成樹上較大的邊就用 satellite channel 來解決

先把 outpost 之間的距離算出來：

vector<edge> E;
for(int v = 0; v < P; v++) {
  scanf("%lf%lf", &C[v].x, &C[v].y);
  for(int u = 0; u < v; u++) E.push_back({u, v, dist(C[u], C[v])});
}

接著將最小生成樹 (network) 上最大的距離找出來：

sort(E.begin(), E.end(), [&](edge A, edge B) { return A.dist < B.dist; });

vector<double> D;
for(edge e: E) {
  int a = Find(e.u), b = Find(e.v);
  if(a != b) {
    D.push_back(e.dist);
    Union(e.u, e.v);
  }
}

printf("%.2lf\n", D[P-S-1]);

練習：

TIOJ 1211 圖論 之 最小生成樹
AIZU 1280 Slim Span
NCPC 2018 Final Problem E Connecting Cities
TIOJ 1445 機器人組裝大賽
TIOJ 1795 咕嚕咕嚕呱啦呱啦

---

Prim 演算法

Prim 維護一個未完成的生成樹
其精神是：每次將樹周遭有最小權重的邊接到樹上，使樹最終成長至最小生成樹

傑出的一手貪心策略

^[5]

Prim 用了兩個重要的觀念：

• 樹是無環的連通圖
• 若圖中只有點沒有任何邊，那麼每個點都是一個獨立的連通塊。

跟 Kruskal 一樣呢

首先隨便找任意點，作為那個初始的"未完成的生成樹"，也就是一塊無環的連通圖

$A$
每次將

$A$ 能觸及到的最小權重的邊接上

$A$，那最終產生的一定是最小權重的生成樹

跟 Kruskal 不同的是，這裡枚舉的是"點"

vector<node> E[maxn]; // maxn 為最大節點數
  :
  .
priority_queue<edge> Q; // 每次挑最小權重的邊
Q.push({1, 1, 0}); // 初始的生成樹 (只有一個點)

while (!Q.empty()) {
  edge e = Q.top(); Q.pop();
  int u = e.v;

  if (vis[u]) continue; // 避免出現環
  vis[u] = true;
  
  cost += e.w;
  MST.push_back(e);
  for (auto v: E[u]) if(!vis[v.id]) Q.push({u, v.id, v.w});
}

複雜度約

$O(|E|{\log }_2|V|)$

練習：

UVa OJ 908 Re-connecting Computer Sites
ACM-ICPC 2005 Southwestern 3505 Buy or Build

A* 搜尋演算法

是路徑搜尋演算法的一個抽象觀點

A* 在節點

$n$ 有個評估函數

$f(n)=g(n)+h(n)$
當

$f(n)$ 大於門檻時就剪枝

$g(n)$ 表示從起點到節點

$n$ 的成本

$h(n)$ 表示從節點

$n$ 到終點的成本

評估函數是根據欲求解問題而設計，討論上是相當自由的

例如：

• 當
  $g(n)$ 是搜尋深度(或最短路步數)， 即 Breadth-first Search 是 A* 的特例
• 有種搜尋法叫做 Best-first Search，
  $h(n)$ 為該節點
  $n$ 到終點的歐幾里得距離

Iterative Deepening A* (IDA*)

IDA* 是種 A* 的變形，會逐步地將門檻變寬

範例 AIZU 1271 Power Calculus：

直覺的，將所有羃次 (p) 的組合全部都試試看，找出最小的操作數 (operations) 就行：

int ans = n; // 操作數至多為 n

void dfs(int d) {
  if (p[d] == n) ans = min(ans, d);
  if (d == n-1) return;

  for (int i = 0; i <= d; i++) {
    p[d+1] = p[d] + p[i];
    dfs(d+1);
    p[d+1] = p[d] - p[i];
    dfs(d+1);
  }
}

執行前先設定邊界(當還未進行操作)：

p[0] = 1;

複雜度為

$O(n^n)$

複雜度頗高，

$n=10$ 的時候就能感受到輸出遲緩了

解答也許在深度還很小的時候就已經能找到了，所以將深度給定一個上限 (ops)：

bool dfs(int d) { // d := depth
  if(p[d] == n) return true;
  if(d == ops) return false;

  for(int i = 0; i <= d; i++) {
    p[d+1] = p[d] + p[i];
    if(dfs(d+1)) return true;
    p[d+1] = p[d] - p[i];
    if(dfs(d+1)) return true;
  }

  return false;
}

接著每次將深度/操作數 (ops) 的上限逐步提高：

while(scanf("%d", &n) && n) {
  for(ops = log2(n);; ops++) if(dfs(0)) break;
  printf("%d\n", ops); // 印出題目要求答案
}

但這題還不只如此，除了 IDA* 門檻設定以外，還得額外剪枝
當剩餘的操作數絕不可能湊出目標羃次 (n) 時，就不繼續以此狀態深入搜尋：

int mx = 0;
for(int i = 0; i <= d; i++) mx = max(mx, p[i]);
if((mx << (ops-d)) < n) return false;

練習：

UVa OJ 11212 Editing a Book
UVa OJ 12558 Egyptian Fractions (HARD version)
UVa OJ 1343 The Rotation Game
UVa OJ 11846 Finding Seats Again
* UVa OJ 11376 Tilt!

Single-Source Shortest Paths

單源最短路徑 (Single-Source Shortest Paths) 簡稱 SSSP。
源點 (Source)，就是起點，通常問題都只是簡單求每條路徑的最小成本。

求單源點到其他所有節點的最短路徑總權重

Relaxation

想像自己在圖中是某一點 v，你看到你的鄰點們 u，他們告訴你：源點走到他們那裡的最小花費成本 cost[u] 是多少，同時你也知道那些點們要過來你這分別要花費多少成本 w (i.e. 邊權重)
考慮源點到自己這的最小成本 cost[v] 得知：

int update = cost[u] + w;
if (update < cost[v]) cost[v] = update;

Dijkstra's Algorithm

Dijkstra's Algo 可看作是 BFS 的帶權重版本

BFS (Breadth-first Search) 的詳細流程複習第四週教材

狀態

$S(n)$ 代表從源點到

$n$ 的最小成本
顯然若

$(u,v)\in E$，則

$S(v)\le S(u)+\text{weight}(u,v)$
所以狀態轉移方程為

$$S(v)=\underset{(u,v)\in E}{min}(S(u)+\text{weight}(u,v))$$

這就是 relaxation

邊界 (源點到源點最小成本)

$$S(\text{source})=0$$

實作上，每次欲更新

$S(v)$ 需從已解的

$S(u)$ 透過

$S(u)+\text{weight}(u,v)$ 做 relaxation
而不斷更新

$S(v)$，終有一刻

$S(v)$ 將得到最優解。此刻就是當

$S(v)$ 小於所有未解的

$S(p)$ 時

這裡

$p$ 是還未得到最優解的點
第十一週投影片有更進一步的解釋

^[6]

vector<node> E[maxn]; // 邊集合

初始源點到任意點的總成本未知，於是將之設為無限大^[7]

memset(s, 0x3f, sizeof(s)); // 源點到任意點的成本初始為無限大
priority_queue<node> Q; // 為從未解集挑出已解的狀態
Q.push({source, s[source] = 0});

接著找出源點到任意點的最短路徑，其就是 BFS 並搭配 Relaxation

while (!Q.empty()) {
  node u = Q.top(); Q.pop();
  
  for (node v: E[u.id]) { // v := 鄰點
    int update = u.w + v.w; // 源點到 u 的最小成本 + u 到 v 的成本
    if (update < s[v.id])
      Q.push({v.id, s[v.id] = update /* relaxation */});
  }
}

其複雜度為

$O(E{\log }_{2}V)$

慢著！演算法的終止條件是 Q.empty() == true，
也就是說，若有個邊權重為負的，則 Q.push({v.id, update}); 將無盡的執行下去。

Bellman's Algo 會提供解決之道

範例 POJ 3255 Roadblocks：

對於點 v 每次將比最短路 d1[v] 還大的更新值 ud 交給次短路 d2[v] 去做 relaxation

priority_queue<node> Q;
int d1[maxn], d2[maxn];

memset(d1, 0x3f, sizeof d1);
memset(d2, 0x3f, sizeof d2);
Q.push({1, d1[1] = 0});

while(!Q.empty()) {
  node u = Q.top(); Q.pop();

  for(node v: E[u.id]) {
    int ud = u.w + v.w; // ud := update

    if(ud < d1[v.id]) {
      Q.push({v.id, ud});
      swap(d1[v.id], ud); // 舊 d1[v.id] 要交給 d2[v.id] 做 relaxation
    }

    if(ud < d2[v.id] && ud > d1[v.id])
      Q.push({v.id, d2[v.id] = ud});
  }
}

練習：

UVa OJ 10986 Sending email
UVa OJ 10801 Lift Hopping

Bellman-Ford's Algorithm

步驟有兩個：

1. 對每一個邊做 relaxation
2. 重複步驟
   $|V|-1$ 次

vector<edge> E;
  :
  .
memset(s, 0x3f, sizeof(s)); // 源點到任意點的成本初始為無限大
s[source] = 0;

for (int i = 0; i < V.size(); i++) // 共 V.size() 個點
  for (edge e: E)
    s[e.v] = min(s[e.v], s[e.u] + e.w);

找單源最短路徑就是這麼簡單

Bellman-Ford's Algo 可以簡單處理權重是負的情況：

• 對每邊做至多
  $|V|-1$ 次 relaxation 後，
• 要是某邊還能 relaxation，就表示有個負權重的邊能使路徑成本一直降低。

範例 UVa OJ 558 Wormholes：

先做

$|V|-1$ 次的每邊 relaxation

fill(s, s+n, INF);
s[0] = 0; // source
 
for(int i = 0; i < n-1; i++)
  for(int j = 0; j < m; j++)
    s[y[j]] = min(s[y[j]], s[x[j]] + t[j]); // relaxtion

接著就能判斷是否能回到過去

for(int j = 0; j < m; j++)
  if(s[x[j]] + t[j] < s[y[j]]) return true; // 還能做 relaxation

return false;

練習：

POJ 2387 Til the Cows Come Home
UVa OJ 10000 Longest Paths

Shortest Path Fast Algorithm (SPFA)

Bellman-Ford’s Algorithm 的進化版本，
其動機是： 若邊被 relax 過，則它的鄰點可以直接進行 relaxation

memset(s, 0x3f, sizeof(s));
s[source] = 0;
memset(in_que, false, sizeof in_que); // in_que := is it in queue?

queue<int> Q;
Q.push(source);
in_que[source] = true;

while (!Q.empty()) {
  int u = Q.front(); Q.pop();
  in_que[u] = false;
  
  for (node v: E[u])
    if (s[v.id] > s[u] + v.w) {
      s[v.id] = s[u] + v.w; // relaxation
      if (!in_que[v.id]) Q.push(v.id), in_que[v.id] = true; // 下次直接讓 v.id 的鄰點做 relaxation
    }
}

長得非常像 Dijkstra’s Algo

最壞複雜度

$O(|V|\cdot |E|)$

平均而言

$O(k\cdot |E|)$， SPFA 提出者認為

$k$ 很小

練習：

UVa OJ 658 It’s not a Bug, it’s a Feature!

All-Pairs Shortest Paths

全點對最短路徑 (All-Pairs Shortest Paths) 簡稱 APSP。
顧名思義，可以得知所有點與點之間的最短路徑，同樣的一般只需求最小花費成本而已。

Floyd-Warshall's Algorithm

設定狀態

$S(i,j,k)$ 為

$i$ 到

$j$ 只許以

$\{1,..,k\}$ 為中間點的最小總成本

而

$i$ 到

$j$ 間

$$S(i,j,k)=\{\begin{array}{ll}S(i,\underset{―}{k},k-1)+S(\underset{―}{k},j,k-1)& \text{若有經過點 }k\\ S(i,j,k-1)& \text{若不經過點 }k\end{array}$$

所以狀態轉移方程：

$$S(i,j,k)=min(S(i,j,k-1),S(i,k,k-1)+S(k,j,k-1))$$

邊界：

$$S(i,j,0)=\{\begin{array}{ll}0& \text{if }i=j\\ \text{weight}(i,j)& \text{if }(i,j)\in E\\ \mathrm{\infty }& \text{if }(i,j)\notin E\end{array}$$

經由滾動陣列優化方法，可使狀態三維降至二維：

同學自行研究，這很簡單的

int s[maxn][maxn];

for (int i = 1; i <= N; i++)
  for (int j = 1; j <= N; j++) s[i][j] = G[i][j];

for (int k = 1; k <= N; k++)
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++)
      s[i][j] = min(s[i][j], s[i][k] + s[k][j]);

範例 UVa OJ 117 The Postal Worker Rings Once：

根據歐拉圖，若有兩點為 odd degree，則終點與卡車並非同一點
也就是說，遇到這個狀況需要算出送件終點與卡車間的最短距離
因為輸入規模很小，直接使用 Floyd-Warshall’s Algo：

Floyd-Warshall’s Algo 很好寫

#include<bits/stdc++.h>
using namespace std;

int const maxn = 27;

string s;
int G[maxn][maxn], deg[maxn];

int main()
{
  while(1) {
    memset(deg, 0, sizeof deg);
    memset(G, 0x3f, sizeof G);
    for(int u = 0; u < maxn; u++) G[u][u] = 0;
    int dist = 0;

    while(cin >> s && s != "deadend") {
      int u = s.front() - 'a', v = s.back() - 'a';
      
      dist += s.length();
      G[u][v] = G[v][u] = min(G[v][u], (int)s.length());
      deg[u]++, deg[v]++;
    }
    if(cin.eof()) return 0;

    vector<int> odd;
    for(int u = 0; u < maxn; u++)
      if(deg[u] & 1) odd.push_back(u);

    if(!odd.empty()) {
      for(int k = 0; k < maxn; k++)
        for(int u = 0; u < maxn; u++)
          for(int v = 0; v < maxn; v++)
            G[u][v] = min(G[u][v], G[u][k] + G[k][v]);

      dist += G[odd[0]][odd[1]];
    }

    cout << dist << endl;
  }

  return 0;
}

練習：

CODEFORCES 320B Ping-Pong (Easy Version)
TIOJ 1096 E.漢米頓的麻煩
Google Code Jam Kickstart Round F 2018 B Specializing Villages: Small dataset
UVa OJ 10724 Road Construction
UVa OJ 125 Numbering Paths
Google Code Jam Round 1B 2017 C Pony Express

---

1. 即任意兩點必有至少一條道路 ↩︎

2. u -> v 表示 u 能走過去到 v; 而 v 不能走到 u ↩︎

3. Wikipedia/ Minimum_spanning_tree.svg ↩︎

4. Wikipedia/ A demo for Kruskal's algorithm based on Euclidean distance. ↩︎

5. Wikipedia/ A demo for Prim's algorithm based on Euclidean distance. ↩︎

6. Wikipedia/ Dijkstra's algorithm runtime ↩︎

7. 也能設為其他具代表性的數字作為未知的總成本 ↩︎