跳转至

最小環

引入

問題

給出一個圖，問其中的由 \(n\) 個節點構成的邊權和最小的環 \((n\ge 3)\) 是多大。

圖的最小環也稱圍長。

過程

暴力解法

設 \(u\) 和 \(v\) 之間有一條邊長為 \(w\) 的邊，\(dis(u,v)\) 表示刪除 \(u\) 和 \(v\) 之間的連邊之後，\(u\) 和 \(v\) 之間的最短路。

那麼無向圖中的最小環是 \(dis(u,v)+w\)。

注意若是在有向圖中求最小環，相對應的公式要修改，最小環是 \(dis(v,u)+w\)。

總時間複雜度 \(O(n^2m)\)。

Dijkstra

相關鏈接：最短路/Dijkstra

過程

枚舉所有邊，每一次求刪除一條邊之後對這條邊的起點跑一次 Dijkstra，道理同上。

性質

時間複雜度 \(O(m(n+m)\log n)\)。

Floyd

相關鏈接：最短路/Floyd

過程

記原圖中 \(u,v\) 之間邊的邊權為 \(val\left(u,v\right)\)。

我們注意到 Floyd 算法有一個性質：在最外層循環到點 \(k\) 時（尚未開始第 \(k\) 次循環），最短路數組 \(dis\) 中，\(dis_{u,v}\) 表示的是從 \(u\) 到 \(v\) 且僅經過編號在 \(\left[1, k\right)\) 區間中的點的最短路。

由最小環的定義可知其至少有三個頂點，設其中編號最大的頂點為 \(w\)，環上與 \(w\) 相鄰兩側的兩個點為 \(u,v\)，則在最外層循環枚舉到 \(k=w\) 時，該環的長度即為 \(dis_{u,v}+val\left(v,w\right)+val\left(w,u\right)\)。

故在循環時對於每個 \(k\) 枚舉滿足 \(i<k,j<k\) 的 \((i,j)\)，更新答案即可。

性質

時間複雜度：\(O(n^3)\)

實現

下面給出 C++ 的參考實現：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
int val[maxn + 1][maxn + 1];  // 原圖的鄰接矩陣

int floyd(const int &n) {
  static int dis[maxn + 1][maxn + 1];  // 最短路矩陣
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) dis[i][j] = val[i][j];  // 初始化最短路矩陣
  int ans = inf;
  for (int k = 1; k <= n; ++k) {
    for (int i = 1; i < k; ++i)
      for (int j = 1; j < i; ++j)
        ans = std::min(ans, dis[i][j] + val[i][k] + val[k][j]);  // 更新答案
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= n; ++j)
        dis[i][j] = std::min(
            dis[i][j], dis[i][k] + dis[k][j]);  // 正常的 floyd 更新最短路矩陣
  }
  return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
val = [[0 for i in range(maxn + 1)] for j in range(maxn + 1)] # 原圖的鄰接矩陣

def floyd(n):
    dis = [[0 for i in range(maxn + 1)] for j in range(maxn + 1)] # 最短路矩陣
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            dis[i][j] = val[i][j] # 初始化最短路矩陣
    ans = inf
    for k in range(1, n + 1):
        for i in range(1, k):
            for j in range(1, i):
                ans = min(ans, dis[i][j] + val[i][k] + val[k][j]) # 更新答案
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]) # 正常的 floyd 更新最短路矩陣
    return ans

例題

GDOI2018 Day2 巡邏

給出一張 \(n\) 個點的無負權邊無向圖，要求執行 \(q\) 個操作，三種操作

  1. 刪除一個圖中的點以及與它有關的邊
  2. 恢復一個被刪除點以及與它有關的邊
  3. 詢問點 \(x\) 所在的最小環大小

對於 \(50\%\) 的數據，有 \(n,q \le 100\)

對於每一個點 \(x\) 所在的簡單環，都存在兩條與 \(x\) 相鄰的邊，刪去其中的任意一條，簡單環將變為簡單路徑。

那麼枚舉所有與 \(x\) 相鄰的邊，每次刪去其中一條，然後跑一次 Dijkstra。

或者直接對每次詢問跑一遍 Floyd 求最小環，\(O(qn^3)\)

對於 \(100\%\) 的數據，有 \(n,q \le 400\)。

還是利用 Floyd 求最小環的算法。

若沒有刪除，刪去詢問點將簡單環裂開成為一條簡單路。

然而第二步的求解改用 Floyd 來得出。

那麼答案就是要求出不經過詢問點 \(x\) 的情況下任意兩點之間的距離。

怎麼在線？

強行離線，利用離線的方法來避免刪除操作。

將詢問按照時間順序排列，對這些詢問建立一個線段樹。

每個點的出現時間覆蓋所有除去詢問該點的時刻外的所有詢問，假設一個點被詢問 \(x\) 次，則它的出現時間可以視為 \(x + 1\) 段區間，插入到線段樹上。

完成之後遍歷一遍整棵線段樹，在經過一個點時存儲一個 Floyd 數組的備份，然後加入被插入在這個區間上的所有點，在離開時利用備份數組退回去即可。

這個做法的時間複雜度為 \(O(qn^2\log q)\)。

還有一個時間複雜度更優秀的在線做法。

對於一個對點 \(x\) 的詢問，我們以 \(x\) 為起點跑一次最短路，然後把最短路樹建出來，順便處理出每個點是在 \(x\) 的哪棵子樹內。

那麼一定能找出一條非樹邊，滿足這條非樹邊的兩個端點在根的不同子樹中，使得這條非樹邊 \(+\) 兩個端點到根的路徑就是最小環。

證明：

顯然最小環包含至少兩個端點在根的不同子樹中一條非樹邊。

假設這條邊為 \((u,v)\)，那麼最短路樹上 \(x\) 到 \(u\) 的路徑是所有 \(x\) 到 \(u\) 的路徑中最短的那條，\(x\) 到 \(v\) 的路徑也是最短的那條，那麼 \(x\to u\to v\to x\) 這個環肯定不會比最小環要長。

那麼就可以枚舉所有非樹邊，更新答案。

每次詢問的複雜度為跑一次單源最短路的複雜度，為 \(O(n^2)\)。

總時間複雜度為 \(O(qn^2)\)。

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用