NO.95十六屆藍橋杯備戰|圖論基礎-單源最短路|負環|BF判斷負環|SPFA判斷負環|郵遞員送信|采購特價產品|拉近距離|最短路計數(C++)

P3385 【模板】負環 - 洛谷

如果圖中存在負環，那么有可能不存在最短路。

BF算法判斷負環

執?n輪松弛操作，如果第n輪還存在松弛操作，那么就有負環。

#include <bits/stdc++.h>
using namespace std;const int N = 2e3 + 10, M = 3e3 + 10;int n, m;
int pos;
struct node
{int u, v, w;
}e[M * 2];int dist[N];bool bf()
{//初始化memset(dist, 0x3f, sizeof dist);dist[1] = 0;bool flg;for (int i = 1; i <= n; i++){flg = false;for (int j = 1; j <= pos; j++){int u = e[j].u, v = e[j].v, w = e[j].w;if (dist[u] == 0x3f3f3f3f) continue;if (dist[u] + w < dist[v]){flg = true;dist[v] = dist[u] + w;}}if (flg == false) return flg;}return flg;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);int T; cin >> T;while (T--){cin >> n >> m;pos = 0;for (int i = 1; i <= m; i++){int u, v, w; cin >> u >> v >> w;pos++;e[pos].u = u, e[pos].v = v, e[pos].w = w;if (w >= 0){pos++;e[pos].u = v, e[pos].v = u, e[pos].w = w;}}if (bf()) cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}

spfa算法判斷負環

維護?個 cnt 數組記錄從起點到該點所經過的邊數，如果 cnt[i] >= n ，說明有負環

#include <bits/stdc++.h>
using namespace std;typedef pair<int, int> PII;const int N = 2e3 + 10, M = 3e3 + 10;int n, m;
vector<PII> edges[N];int dist[N];
bool st[N]; //標記在隊列中
int cnt[N];bool spfa()
{//初始化memset(dist, 0x3f, sizeof dist);memset(st, 0, sizeof st);memset(cnt, 0, sizeof cnt);queue<int> q;q.push(1);dist[1] = 0;st[1] = true;while (q.size()){auto u = q.front(); q.pop();st[u] = false;for (auto& t : edges[u]){int v = t.first, w = t.second;if (dist[u] + w < dist[v]){dist[v] = dist[u] + w;cnt[v] = cnt[u] + 1;if (cnt[v] >= n) return true;if (!st[v]){q.push(v);st[v] = true;}}}}return false;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);int T; cin >> T;while (T--){cin >> n >> m;for (int i = 1; i <= n; i++) edges[i].clear();for (int i = 1; i <= m; i++){int u, v, w; cin >> u >> v >> w;edges[u].push_back({v, w});if (w >= 0) edges[v].push_back({u, w});}if (spfa()) cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}


	常規版-dijkstra	堆優化-dijkstra	bellman?ford算法	spfa算法
算法思想	貪? ? 每次拿出還未確定最短路的點中，距離起點最近的點； ? 打上標記之后，更新出邊所連點的最短路。	使?堆優化找點操作： ? 把還未確定最短路的點扔到堆中，?堆快速找出距離起點最近的點。	暴?松弛： ? 執?n-1輪松弛操作； ? 每次都掃描所有的邊，看看能否松弛。	使?隊列優化bf算法： ? 只有上?輪被松弛的點，下?輪才有可能松弛。
負邊權	失效	失效	可?	可?
負環	失效	失效	可以判斷負環： ? 執?n輪操作，判斷是否松弛	可以判斷負環： ? 創建cnt數組，標記從起點到該點的邊數
時間復雜度	O(n2)	O(mlog m)	O(nm)	O(km) ~O(nm)

其實還有兩個單源最短路算法，那就是普通bfs以及01bfs：

普通bfs只能處理邊權全部相同且?負的最短路；
01bfs只能解決邊權要么為0，要么為1的情況

P1629 郵遞員送信 - 洛谷

從起點找別的點的最短距離很簡單，直接跑各種最短路算法均可。
但是從別的點回到起點的最短路，如果直接求時間復雜度巨?。思考?件事：

假設從某?點z，到達起點的最短路徑為：z->y->x->s；
那么反過來就是s->x->y->z的最短路徑。
因此，僅需對原圖的所有圖建??個"反圖"，然后跑?遍最短路即可。這就是建"反圖"的技巧

#include <bits/stdc++.h>
using namespace std;const int N = 1e3 + 10;int n, m;
int e[N][N];int dist[N];
bool st[N];void dijkstra()
{memset(dist, 0x3f, sizeof dist);memset(st, 0, sizeof st);dist[1] = 0;for (int i = 1; i <= n; i++){int a = 0;for (int j = 1; j <= n; j++)if (!st[j] && dist[j] < dist[a])a = j;st[a] = true;for (int b = 1; b <= n; b++){int c = e[a][b];if (dist[a] + c < dist[b]){dist[b] = dist[a] + c;}}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;memset(e, 0x3f, sizeof e);for (int i = 1; i <= m; i++){int a, b, c; cin >> a >> b >> c;e[a][b] = min(e[a][b], c);}dijkstra();int ret = 0;for (int i = 1; i <= n; i++) ret += dist[i];//反圖for (int i = 1; i <= n; i++)for (int j = i+1; j <= n; j++)swap(e[i][j], e[j][i]);dijkstra();for (int i = 1; i <= n; i++) ret += dist[i];cout << ret << endl;return 0;
}

P1744 采購特價商品 - 洛谷

看數據范圍，所有的最短路算法均可解決，這?使?BF算法。
?需建圖，只?把所有的邊存下來。注意是?向邊，所以要存兩次，空間也要開兩倍。
在所有邊上做?次bf算法，輸出結果即可

#include <bits/stdc++.h>
using namespace std;const int N = 110, M = 1010;int n, m, s, t;
double x[N], y[N];struct node
{int a, b;double c;
}e[M];double calc(int i, int j)
{double dx = x[i] - x[j];double dy = y[i] - y[j];return sqrt(dx * dx + dy * dy);
}double dist[N];void bf()
{for (int i = 1; i <= n; i++) dist[i] = 1e10;dist[s] = 0;for (int i = 1; i < n; i++){for (int j = 1; j <= m; j++){int a = e[j].a, b = e[j].b;double c = e[j].c;if (dist[a] + c < dist[b]){dist[b] = dist[a] + c;}if (dist[b] + c < dist[a]){dist[a] = dist[b] + c;}}}
}int main()
{cin >> n;for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];cin >> m;for (int i = 1; i <= m; i++){int a, b; cin >> a >> b;e[i].a = a; e[i].b = b; e[i].c = calc(a, b);}cin >> s >> t;bf();printf("%.2lf\n", dist[t]);return 0;
}

P2136 拉近距離 - 洛谷

bf算法判斷負環即可。但要注意?下細節：

題?中給的是距離w是能縮?的數，因此存邊的時候，應該存成相反數；
愛情是雙向奔赴的，我們要在1->n和n->1兩種情況??選擇最?值

#include <bits/stdc++.h>
using namespace std;const int N = 1e3 + 10, M = 1e4 + 10;int n, m;
struct node
{int a, b, c;
}e[M];int dist[N];bool bf(int s)
{memset(dist, 0x3f, sizeof dist);dist[s] = 0;bool flg;for (int i = 1; i <= n; i++){flg = false;for (int j = 1; j <= m; j++){int a = e[j].a, b = e[j].b, c = e[j].c;if (dist[a] + c < dist[b]){flg = true;dist[b] = dist[a] + c;}}if (flg == false) return flg;}return flg;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= m; i++){cin >> e[i].a >> e[i].b >> e[i].c;e[i].c = -e[i].c;}int ret;bool st = bf(1);if (st){cout << "Forever love" << endl;return 0;}ret = dist[n];st = bf(n);if (st){cout << "Forever love" << endl;return 0;}cout << min(ret, dist[1]) << endl;return 0;
}

P1144 最短路計數 - 洛谷

解法?：bfs+動態規劃

因為邊權全都相等，所以可以?bfs找出最短路；
在bfs找最短路的過程中，更新最短路的條數。
動態規劃：

狀態表?：設 f[i] 表?從起點?到 i 點的最短路的條數。
狀態轉移?程： f[i] += f[prev] 。
其中 prev 表? i 點的所有前驅，但是要注意是通過最短路過來的前驅。
填表順序：按照bfs的順序填表。
解法?：dijkstra算法+動態規劃
這種解法更通?，因為即使邊權不相等，也可以?dj算法

#include <bits/stdc++.h>
using namespace std;typedef pair<int, int> PII;
const int N = 1e6 + 10, M = 2e6 + 10, MOD = 100003;int n, m;
vector<int> edges[N];int dist[N];
bool st[N];
int f[N];void bfs()
{memset(dist, 0x3f, sizeof dist);queue<int> q;q.push(1);dist[1] = 0;f[1] = 1;while (q.size()){auto a = q.front(); q.pop();for (auto b : edges[a]){if (dist[a] + 1 < dist[b]){dist[b] = dist[a] + 1;f[b] = f[a];q.push(b);}else if (dist[a] + 1 == dist[b]){f[b] = (f[b] + f[a]) % MOD;}}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= m; i++){int a, b; cin >> a >> b;edges[a].push_back(b);edges[b].push_back(a);}bfs();for (int i = 1; i <= n; i++) cout << f[i] << endl;return 0;
}

#include <bits/stdc++.h>
using namespace std;typedef pair<int, int> PII;
const int N = 1e6 + 10, M = 2e6 + 10, MOD = 100003;int n, m;
vector<int> edges[N];int dist[N];
bool st[N];
int f[N];void dijkstra()
{memset(dist, 0x3f, sizeof dist);priority_queue<PII, vector<PII>, greater<PII>> heap;heap.push({0, 1});dist[1] = 0;f[1] = 1;while (heap.size()){auto t = heap.top(); heap.pop();int a = t.second;if (st[a]) continue;st[a] = true;for (auto b : edges[a]){if (dist[a] + 1 < dist[b]){dist[b] = dist[a] + 1;f[b] = f[a];heap.push({dist[b], b});}else if (dist[a] + 1 == dist[b]){f[b] = (f[a] + f[b]) % MOD;}}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m;for (int i = 1; i <= m; i++){int a, b; cin >> a >> b;edges[a].push_back(b);edges[b].push_back(a);}dijkstra();for (int i = 1; i <= n; i++) cout << f[i] << endl;return 0;
}