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算法判断负环即可。但要注意⼀下细节：

1. 题⽬中给的是距离w是能缩⼩的数，因此存边的时候，应该存成相反数；
2. 爱情是双向奔赴的，我们要在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找最短路的过程中，更新最短路的条数。
  动态规划：

1. 状态表⽰：设 f[i] 表⽰从起点⾛到 i 点的最短路的条数。
2. 状态转移⽅程： f[i] += f[prev] 。
   其中 prev 表⽰ i 点的所有前驱，但是要注意是通过最短路过来的前驱。
3. 填表顺序：按照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;
}