图论
图论
本文将介绍Dijkstra、Bellman-Ford、SPFA、Floyd等算法
注意：本文图文并茂
将提供以下图文链接供大家理解：
图文链接：
飞书图解链接🎉🎉🎉
密码：L1@75666
1. Dijkstra算法
题目1
#include<bits/stdc++.h>
using namespace std;
const int N = 5e2 + 10, M = 1e5 + 10, INF = 0x3f3f3f3f;
int g[N][N], dist[N];
bool st[N];
int n, m;
int dijkstra(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 1; i < n; i ++ ){
int t = 0;
for(int j = 1; j <= n; j ++ ){
if(!st[j] && dist[t] > dist[j]) t = j;
}
for(int j = 1; j <= n; j ++ ){
if(dist[j] > dist[t] + g[t][j]){
dist[j] = dist[t] + g[t][j];
}
}
st[t] = true;
}
if(dist[n] == INF) return -1;
else return dist[n];
}
int main(){
memset(g, 0x3f, sizeof g);
scanf("%d%d", &n, &m);
int a, b, c;
while(m -- ){
scanf("%d%d%d", &a, &b, &c);
g[a][b] = min(g[a][b], c);
}
printf("%d\n", dijkstra());
for(int i = 0; i <= n; i ++ ){
printf("%s ", st[i] ? "true" : "false");
}
puts("");
return 0;
}
题目2
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10, M = 5e5 + 10, INF = INT_MAX;
struct edge{
int v, w;
};
int dist[N];
bool st[N];
vector<edge> e[N];
int n, m, s;
void dijkstra(int a){
for(int i = 0; i <= n; i ++ ) dist[i] = INF;
dist[a] = 0;
for(int i = 1; i < n; i ++ ){
int t = 0;
for(int j = 1; j <= n; j ++ ){
if(!st[j] && dist[t] > dist[j]) t = j;
}
st[t] = true;
for(auto &edge: e[t]){
int v = edge.v, w = edge.w;
if(dist[v] > dist[t] + w) dist[v] = dist[t] + w;
}
}
}
int main(){
scanf("%d%d%d", &n, &m, &s);
int a, b, c;
while(m -- ){
scanf("%d%d%d", &a, &b, &c);
e[a].push_back({b, c});
}
dijkstra(s);
for(int i = 1; i <= n; i ++ ){
printf("%d ", dist[i]);
}
return 0;
}
题目3
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, M = 2e5 + 10, INF = INT_MAX;
struct edge{
int v, w;
};
int dist[N];
bool st[N];
int n, m, s;
vector<edge> e[N];
priority_queue<PII, vector<PII>, greater<PII>> q;
void dijkstra(int s){
for(int i = 0; i <= n; i ++ ) dist[i] = INF;
dist[s] = 0;
q.push({0, s}); // PII = {dist, edge} edge 到点 s 的距离dist
while(q.size()){
auto t = q.top();
q.pop();
int u = t.second;
if(st[u]) continue;
st[u] = true;
for(auto &edge : e[u]){
int v = edge.v, w = edge.w;
if(dist[v] > dist[u] + w){
dist[v] = dist[u] + w;
q.push({dist[v], v});
}
}
}
}
int main(){
scanf("%d%d%d", &n, &m, &s);
int a, b, c;
while(m -- ){
scanf("%d%d%d", &a, &b, &c);
e[a].push_back({b, c});
}
dijkstra(s);
for(int i = 1; i <= n; i ++ ){
printf("%d ", dist[i]);
}
return 0;
}
题目4
题意如下：
E - 滑雪
AtCoder 滑雪场有\(N\)个开放区，分别是Space 1， Space 2，...，Space N. Space \(i\) 的海拔是\(H_i\)，有\(M\)个斜坡双向连接两个Space. 第\(i(1 \leq i \leq M)\)个斜坡连接Space \(U_i\)和\(V_i\). 在任意两个空间之间使用一些斜坡是可能的。Takahashi仅通过斜坡从一个Space通过另一个Space. 每次通过一个斜坡他的幸福感改变. 具体地说，当他使用斜坡从Space \(X\) 到 Space \(Y\)，他的幸福感变化如下:
- 如果Space \(X\)的海拔严格高于 Space \(Y\)，他的幸福感增加\(H_X - H_Y\).
- 如果Space \(X\)的海拔严格低于 Space \(Y\)，他的幸福感下降\(2 \times (H_Y - H_X)\).
- 如果Space \(X\)的海拔等于 Space \(Y\)，他的幸福感不变.
幸福感可能是负值.
起初，Takahashi在Space 1,并且他的幸福感是0，找到他在通过任意数量（可能是0）的斜坡之后最大可能的幸福感，停止在任何Space.
数据范围：
- \(2 \leq N \leq 2 \times 10^5\)
- \(N - 1 \leq M \leq min(2 \times 10^5, \frac {N(N - 1)}{2})\)
- \(0 \leq H_i \leq 10^8 (1 \leq i \leq N)\)
- \(1 \leq U_i < V_i \leq N (1 \leq i \leq M)\)
- \((U_i,V_i) \neq (U_j,V_j) \quad if \quad i \neq j\)
- 输入的所有值是整数
- 在任意两个Space之间使用一些斜坡是可能的(重边)。
输入：
N M
H1 H2 ... HN
U1 V1
U2 V2
.
.
.
UM VM
输出：
打印答案。
样例输入1:
4 4
10 8 12 5
1 2
1 3
2 3
3 4
样例输出1：
3
样例解释：
如果 Takahashi 从 Space 1 -> Space 3 -> Space 4,他的幸福感变化如下：
- 当他从Space1(海拔10)到Space3(海拔12)，他的幸福感下降\(2 \times (12 - 10) = 4\)，幸福感变为\(-4\).
- 当他从Space3(海拔12)到Space4(海拔5)他的幸福感上升\(12 - 5 = 7\),并且变为了(-4 + 7 = 3)
如果他结束滑雪，最终的幸福感是3，这是最大可能的值。
样例输入2:
2 1
0 10
1 2
样例输出2：
0
他一点不移动的幸福感最大。
题解如下
AC代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e5 + 10, INF = INT_MAX;
struct edge{
int v, w;
};
LL dist[N];
int h[N];
bool st[N];
int n, m;
vector<edge> e[N];
priority_queue<PII, vector<PII>, greater<PII>> q;
void dijkstra(int s){
for(int i = 0; i <= n; i ++ ) dist[i] = INF;
dist[s] = 0;
q.push({0, s}); // PII = {dist, edge} edge 到点 s 的距离dist
while(q.size()){
auto t = q.top();
q.pop();
int u = t.second;
if(st[u]) continue;
st[u] = true;
for(auto &edge : e[u]){
int v = edge.v, w = edge.w;
if(dist[v] > dist[u] + w){
dist[v] = dist[u] + w;
q.push({dist[v], v});
}
}
}
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
int u, v;
while(m -- ){
scanf("%d%d", &u, &v);
if(h[u] > h[v]){ // h[u] > h[v]
e[u].push_back({v, 0});
e[v].push_back({u, h[u] - h[v]});
}else{ // h[v] > h[u]
e[v].push_back({u, 0});
e[u].push_back({v, h[v] - h[u]});
}
}
dijkstra(1);
LL ans = 0;
for(int i = 1; i <= n; i ++ ){
if(dist[i] == INF) continue;
ans = max(ans, -(dist[i] - h[1] + h[i]));
}
printf("%lld\n", ans);
return 0;
}
2. Bellman-Ford算法
题目1
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10, INF = 0x3f3f3f3f;
struct edge{
int v, w;
};
vector<vector<edge>> e(N);
int dist[N], cnt[N]; // cnt 表示点i距离远点的边数
bool st[N];
queue<int> q;
int T, n, m;
bool bellman_ford(int s){
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
bool flag; // 是否松弛
for(int i = 1; i <= n; i ++ ){
flag = false;
for(int u = 1; u <= n; u ++ ){
if(dist[u] == INF) continue;
for(auto const &edge : e[u]){
int v = edge.v, w = edge.w;
if(dist[v] > dist[u] + w){
dist[v] = dist[u] + w;
flag = true;
}
}
}
if(!flag) break;
}
return flag;
}
int main(){
scanf("%d", &T);
int a, b, c;
while(T -- ){
e.clear();
e.resize(N);
scanf("%d%d", &n, &m);
while(m -- ){
scanf("%d%d%d", &a, &b, &c);
if(c >= 0) e[b].push_back({a, c});
e[a].push_back({b, c});
}
printf("%s\n", bellman_ford(1) ? "YES" : "NO");
}
return 0;
}
3. SPFA算法
题目1
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10, INF = 0x3f3f3f3f;
struct edge{
int v, w;
};
vector<vector<edge>> e;
int dist[N], cnt[N];
bool st[N];
queue<int> q;
int T, n, m;
bool spfa(int s){
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
st[s] = true;
q.push(s);
while(q.size()){
int u = q.front();
q.pop();
st[u] = false;
for(auto const &edge : e[u]){
int v = edge.v, w = edge.w;
if(dist[v] > dist[u] + w){
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(){
scanf("%d", &T);
while(T -- ){
e.clear();
e.resize(N);
// 清空 q
while(!q.empty()) q.pop();
memset(cnt, 0, sizeof cnt);
memset(st, 0, sizeof st);
scanf("%d%d", &n, &m);
int a, b, c;
while(m -- ){
scanf("%d%d%d", &a, &b, &c);
if(c >= 0) e[b].push_back({a, c});
e[a].push_back({b, c});
}
printf("%s\n", spfa(1) ? "YES" : "NO");
}
return 0;
}
题目2
TODO
4. Floyd算法
题目1
#include<bits/stdc++.h>
using namespace std;
const int N = 2e2 + 10, INF = 0x3f3f3f3f;
int g[N][N];
int n, m, q;
void floyd(){
for(int k = 1; k <= n; k ++ )
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
int main(){
scanf("%d%d%d", &n, &m, &q);
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= n; j ++ ){
if(i == j) g[i][j] = 0;
else g[i][j] = INF;
}
}
int a, b, c;
while(m -- ){
scanf("%d%d%d", &a, &b, &c);
g[a][b] = min(g[a][b], c);
}
floyd();
while(q -- ){
scanf("%d%d", &a, &b);
if(g[a][b] > INF / 2) puts("impossible");
else printf("%d\n", g[a][b]);
}
return 0;
}