NO.96十六屆藍橋杯備戰|圖論基礎-多源最短路|Floyd|Clear And Present Danger|災后重建|無向圖的最小環問題(C++)

多源最短路：即圖中每對頂點間的最短路徑
![[Pasted image 20250417140843.png]]

floyd算法本質是動態規劃，?來求任意兩個結點之間的最短路，也稱插點法。通過不斷在兩點之間加?新的點，來更新最短路。
適?于任何圖，不管有向?向，邊權正負，但是最短路必須存在（也就是不存在負環）。

狀態表?： f[k][i][j] 表?：僅僅經過 [1, k] 這些點，結點 i ?到結點 j 的最短路徑的?度。
狀態轉移?程：

第?種情況，不選新來的點： f[k][i][j] = f[k - 1][i][j] ；
第?種情況，選擇新來的點： f[k][i][j] = f[k - 1][i][k] + f[k - 1][k][j]

空間優化：只會?到上?層的狀態，因此可以優化到第?維。
初始化：

f[i][i] = 0 ；
f[i][j] 為初始狀態下 i 到 j 的距離，如果沒有邊則為?窮。

填表順序：

?定要先枚舉 k ，再枚舉 i 和 j 。因為我們填表的時候，需要依賴的是 k - 1 層的狀態，因此 k 必須先枚舉。

B3647 【模板】Floyd - 洛谷

#include <bits/stdc++.h>
using namespace std;const int N = 110;int n, m;
int f[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;memset(f, 0x3f, sizeof f);for (int i = 1; i <= n; i++) f[i][i] = 0;for (int i = 1; i <= m; i++){int a, b, c; cin >> a >> b >> c;f[a][b] = f[b][a] = min(f[a][b], c);}//floydfor (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)f[i][j] = min(f[i][j], f[i][k] + f[k][j]);for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++)cout << f[i][j] << " ";cout << endl;}return 0;
}

P2910 [USACO08OPEN] Clear And Present Danger S - 洛谷

#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 110, M = 1e4 + 10;int n, m;
int a[M];
int f[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= m; i++) cin >> a[i];for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)cin >> f[i][j];for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)f[i][j] = min(f[i][j], f[i][k] + f[k][j]);LL ret = 0;for (int i = 2; i <= m; i++){int x = a[i-1], y = a[i];ret += f[x][y];}cout << ret << endl;return 0;
}

P1119 災后重建 - 洛谷

在floyd算法中，我們是?個點?個點加?到最短路的更新中，那么這道題其實就是限制了我們加點的時機。當從前往后遍歷每次詢問的時候，直到時間點在詢問的時間t之前的點，都可以加?到最短路的更新中。
那么就可以?邊讀取詢問，?邊通過時間限制，更新最短路

#include <bits/stdc++.h>
using namespace std;const int N = 210, INF = 0x3f3f3f3f;int n, m;
int t[N];
int f[N][N];void floyd(int k)
{for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 0; i < n; i++) cin >> t[i];memset(f, 0x3f, sizeof f);for (int i = 0; i < n; i++) f[i][i] = 0;for (int i = 1; i <= m; i++){int a, b, c; cin >> a >> b >> c;f[a][b] = f[b][a] = min(f[a][b], c);}int Q; cin >> Q;int pos = 0;while (Q--){int a, b, c; cin >> a >> b >> c;while (pos < n && t[pos] <= c) floyd(pos++);if (t[a] > c || t[b] > c || f[a][b] == INF) cout << -1 << endl;else cout << f[a][b] << endl;}return 0;
}

P6175 無向圖的最小環問題 - 洛谷

floyd算法的性質：

在計算第 k 層的時候， f[i][j] ??存儲著中轉點為 [1, k - 1] 時的最短路。如果設環?的最?結點的編號為 k ，與k相鄰的點為 i, j ，其中 i < k && j < k && i != j ：
那么我們在floyd算法循環到 k 的時候，這個環的最??度為： f[i][j] + e[i][k] + e[j][k] 。
環的最?編號是任意的，因此在所有情況下取最?值即可

#include <bits/stdc++.h>
using namespace std;const int N = 110, INF = 1e8;int n, m;
int e[N][N];
int f[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;//memset(e, 0x3f, sizeof e);//memset(f, 0x3f, sizeof f);for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)f[i][j] = e[i][j] = INF;for (int i = 1; i <= n; i++) e[i][i] = f[i][i] = 0;for (int i = 1; i <= m; i++){int a, b, c; cin >> a >> b >> c;e[a][b] = e[b][a] = f[a][b] = f[b][a] = min(e[a][b], c);}int ret = INF;for (int k = 1; k <= n; k++){//最小環for (int i = 1; i < k; i++)for (int j = i+1; j < k; j++)ret = min(ret, f[i][j] + e[i][k] + e[k][j]);//最短距離for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)f[i][j] = min(f[i][j], f[i][k] + f[k][j]);}if (ret == INF) cout << "No solution." << endl;else cout << ret << endl;return 0;
}