最短路
最短路算法
- Floyd 算法：多源最短路
- Dijkstra 算法：单源最短路
- SPFA 算法：判负环
- 特殊图最短路：
- 带负权最短路
- 次短路
- 边权只有 0/1 的最短路
次短路
-
最短路树：求出最短路后，每个源点 i 有且仅有一个转移过来的父亲，形成了一个树形结构
-
这张图上还有一些非树边
-
次短路性质：本质上是经过不超过一条非树边的路
-
因为走树边永远比非树边要更优
-
枚举一条不在最短路上的非树边 x\to y ，强制经过该边，其他走的边都在树边上
for (（x，y）不在最短路上) ans = min(ans,dis[x] + w[x,y] + dis[y]); -
可以拓展到 k 短路 （复杂度 O(k\log m) ）
差分约束系统
- 如果是 x_i -x_j\ge c_k ？ 反过来建边
- 把所有关系全部转化为 x_i\le x_j+c_k
- x_i 能取的区间就是所有限制上最紧的
- 如果是张 DAG 就可以直接 dp 出来
- 如果不是？
- 建一个虚拟节点 s ，连几条向起点、边权 0 的边
- 如果最短路可解，则差分约束系统就可解
- 如果要求某个元素最大，就求最短路
- 如果要求某个元素最小，就求最长路
- 差分约束详解
有向图最小环
- Floyd 求解
例题
P5304 [GXOI/GZOI2019] 旅行者
给定一个 n 个点 m 条边的有向带权图，其中有 k 个特殊点，求这 k 个特殊点之间两两最短路的最小值
- 把这 k 个点按照二进制分组
- 当前位为 0 的点扔进起点集合，当前位为 1 的点扔进终点集合
- 时间复杂度 O(dis\log m)
例题3
给定一个无向带权连通图，求节点两两之间最短路径从小到大排序之后第 k 长的路径的长度
- 肯定不会用到经过比第 k 小的边还小的路径
- 所以可以删掉这些边
- 这样删下来只会剩下至多 800 个点
例题4
给定一张 N 个点 N 条边的有向图，每个点出度为 1
求最少增加多少条有向边使得：从 1 到每个点的最短路径不大于 K 。
1\le N\le 10^6
- 先把所有叶子节点和 1 进行连边
- 从叶子节点往上走并更新答案
- 这样就只会剩下一个环
- 先把已经满足要求的点染色
- 枚举起点从 1 到 k 时答案会怎么样
Shortest Path
- 设状态 f[i][j] 表示当前为 j ，前一个为 i 时的答案
- 转移时如果 i 是 a_x 且 j 是 b_x ，那就不能向 f[j][c_x] 转移
- 此时如果 i 和 j 不满足上面的要求，可以直接记录状态为 f[0][j] ，减少状态数
P1363 幻象迷宫
-
所以不能拓展迷宫而对坐标取模就好了.
-
如果走到过某个点现在又走到了这个点，那显然是可以走无限远的。
-
现在出现了一些~~（堆）~~问题：如何判断是否走到过这个点呢？
-
有一个比较巧妙的方法：
-
记录取模的横纵坐标 x,y 时，同时记录没有取模的坐标 lx, ly
-
当第一次走这个迷宫的时候， x, y 和 lx, ly 肯定是分别相等的
-
所以只要走到的一个点的 x, y 和 lx, ly 不相等
x≠lx ∣∣ y≠lyx\\=lx ∣∣ y\\=ly，
-
那这个点一定是被走了第二遍
故乡的梦
给出一个带权无向图，起点 S 和终点 T 。 Q 个询问。每个询问询问删除某条边后 S 到 T 的最短路。 1\le N,M,Q\le2\times10^5
P4246 [SHOI2008] 堵塞的交通
- 线段树维护区间连通信息（4个点&上下两个点）
- 剩下就是代码问题（悲
课后题
[JSOI2007]重要的城市
-
跑 Floyd ，如果当前中转点 k 能更新 f[i][j] 的答案，那 k 就是 (i,j) 的重要城市
-
如果 (i,j) 存在不止一条最短路，那 (i,j) 就没有重要城市
#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn = 205; bool ans[maxn]; int n,m; ll mp[maxn][maxn]; int imp[maxn][maxn]; int main () { scanf("%d%d",&n,&m); for (int i = 1;i <= n;i ++) for (int j = 1;j <= n;j ++) if (i != j) mp[i][j] = 1e18; for (int i = 1,x,y,v;i <= m;i ++) { scanf("%d%d%d",&x,&y,&v); mp[y][x] = mp[x][y] = (ll)(v); } for (int k = 1;k <= n;k ++) for (int i = 1;i <= n;i ++) for (int j = 1;j <= n;j ++) if (i != j && j != k && i != k) { if (mp[i][j] > mp[i][k] + mp[k][j]) mp[i][j] = mp[i][k] + mp[k][j],imp[i][j] = k; else if (mp[i][j] == mp[i][k] + mp[k][j]) imp[i][j] = -1; } for (int i = 1;i <= n;i ++) for (int j = 1;j <= n;j ++) if (imp[i][j] != -1) ans[imp[i][j]] = true; bool ok = true; for (int i = 1;i <= n;i ++) if (ans[i]) { printf("%d ",i); ok = false; } if (ok) printf("No important cities."); return 0; }
CQOI新年好
-
对每个亲戚都跑一遍最短路，暴力枚举亲戚的先后访问顺序
#include<bits/stdc++.h> #define type pair<int,int> #define int long long #define mk make_pair using namespace std; const int maxn = 200005; int n,m,s[10],dis[10][maxn],ans = 2e9; vector<type> mp[maxn]; bool vis[maxn]; void addEdge(int u,int v,int w) { mp[u].push_back(mk(v,w)); } void Dijkstra(int id) { priority_queue<type,vector<type>,greater<type> > q; dis[id][s[id]] = 0; q.push(mk(0,s[id])); while (!q.empty()) { type top = q.top(); q.pop(); int u = top.second; vis[u] = true; for (auto v : mp[u]) if (dis[id][v.first] > dis[id][u] + v.second) { dis[id][v.first] = dis[id][u] + v.second; if (!vis[v.first]) q.push(mk(dis[id][v.first],v.first)); } } memset(vis,0,sizeof(vis)); } void dfs(int pos,int lst, int sum) { if (pos > 6) { ans = min(ans,sum); return ; } if (sum > ans) return ; for (int i = 2;i <= 6;i ++) if (!vis[i] && dis[lst][s[i]] != 0x3f3f3f3f) { vis[i] = true; dfs(pos + 1,i,sum + dis[lst][s[i]]); vis[i] = false; } } signed main() { scanf("%lld%lld",&n,&m); s[1] = 1; memset(dis,0x3f,sizeof(dis)); for (int i = 2;i <= 6;i ++) scanf("%lld",&s[i]); for (int i = 1,u,v,w;i <= m;i ++) { scanf("%lld%lld%lld",&u,&v,&w); addEdge(u,v,w); addEdge(v,u,w); } for (int i = 1;i <= 6;i ++) Dijkstra(i); dfs(2,1,0); printf("%lld",ans); } /* 6 6 2 3 4 5 6 1 2 8 2 3 3 3 4 4 4 5 5 5 6 2 */
JLOI2011飞行路线
-
设 dp[i][j] 表示当前转移到 i 点，使用 j 条免费路线
-
初始化 dp[i][0] 为起点到 i 的最短路
-
用求最短路的方法进行转移，假设当前点为 u ，要从 v 转移状态
-
dp[u][j] = \min(dp[v][j - 1],dp[v][j] + w[u\to v])
-
枚举 j 从 1\to k 转移状态
-
答案从 dp[t][0\to k] 取 \min
/* dp[i][k] -> 从起点飞到i城市，使用k条免费路线的最小代价 初始化 -> d[i][0] = 从起点到这里的最短路 转移 -> d[v][k] = min(d[u][k - 1],d[u][k] + w) 答案在d[终点][0 ~ k] 中取min 徒手切爆蓝题了耶 qwq */ #include<bits/stdc++.h> #define mk make_pair #define type pair<int,int> using namespace std; const int maxn = 10005,maxk = 15; bool vis[maxn]; int n,m,k,s,t,dp[maxn][maxk],dis[maxn],ans = 2e9; vector<type> mp[maxn]; void addEdge(int u,int v,int w) { mp[u].push_back(mk(v,w)); } void Init() { priority_queue<type,vector<type>,greater<type> > q; memset(dis,0x3f,sizeof(dis)); dis[s] = 0; q.push(mk(0,s)); while (!q.empty()) { type top = q.top(); q.pop(); int u = top.second; vis[u] = true; for (auto v : mp[u]) if (dis[v.first] > dis[u] + v.second) { dis[v.first] = dis[u] + v.second; if (!vis[v.first]) q.push(mk(dis[v.first],v.first)); } } memset(dp,0x3f,sizeof(dp)); for (int i = 1;i <= n;i ++) dp[i][0] = dis[i]; } void Solve() { priority_queue<type,vector<type>,greater<type> > q; memset(vis,false,sizeof(vis)); q.push(mk(dp[s][0],s)); while (!q.empty()) { type top = q.top(); q.pop(); int u = top.second; vis[u] = true; for (auto v : mp[u]) for (int i = 1;i <= k;i ++) if (dp[v.first][i] > min(dp[u][i] + v.second,dp[u][i - 1])) { dp[v.first][i] = min(dp[u][i] + v.second,dp[u][i - 1]); if (!vis[v.first]) q.push(mk(dp[v.first][i],v.first)); } } } int main() { scanf("%d%d%d%d%d",&n,&m,&k,&s,&t); s ++, t ++; // 下标统一从1开始 for (int i = 1,u,v,w;i <= m;i ++) { scanf("%d%d%d",&u,&v,&w); addEdge(u + 1,v + 1,w); addEdge(v + 1,u + 1,w); } Init(); Solve(); for (int i = 0; i <= k;i ++) ans = min(ans,dp[t][i]); printf("%d",ans); return 0; }
护送
-
Floyd
-
设边的最短路转移矩阵为 f ，加上点权后的最短路转移矩阵为 g
-
按照点权从小到大进行转移
-
g[i][j] = \min(f[i][j] + v[k]) 其中 v 表示点权， k 为中转点
#include <bits/stdc++.h> #define ll long long using namespace std; const int maxn = 605; struct hyf { int id; ll value; } c[maxn]; ll nc[maxn], f[maxn][maxn], g[maxn][maxn]; int n, m, q; bool cmp(const hyf &x, const hyf &y) { return x.value < y.value; } int main() { scanf("%d%d", &n, &m); memset(f, 127 / 3, sizeof(f)); memset(g, 127 / 3, sizeof(g)); for (int i = 1; i <= n; i ++) { scanf("%lld", &c[i].value); nc[i] = c[i].value, c[i].id = i; } for (int i = 1, u, v; i <= m; i ++) { ll w; scanf("%d%d%lld", &u, &v, &w); f[u][v] = f[v][u] = min(f[u][v], w); } sort(c + 1, c + n + 1, cmp); for (int t = 1,k; t <= n; t++) { k = c[t].id; for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) if (f[i][j] >= (f[i][k] + f[k][j])) f[i][j] = f[i][k] + f[k][j]; for (int i = 1; i <= t; i ++) for (int j = 1; j <= t; j ++) g[c[i].id][c[j].id] = min(g[c[i].id][c[j].id], f[c[i].id][c[j].id] + c[t].value); } scanf("%d", &q); for (int i = 1, s, t; i <= q; i ++) { scanf("%d%d", &s, &t); printf("%lld\n", g[s][t]); } return 0; }
种树
-
差分约束 + 前缀和
-
可以建立出三个约束：(设树棵树的前缀和数组为 sum )
- sum[r]-sum[l-1]\ge c
- sum[i]-sum[i-1]\ge 0
- sum[i-1]-sum[i]\ge -k
-
按照上述约束建边，SPFA 跑最长路即可
#include<bits/stdc++.h> #define ll long long #define mk make_pair using namespace std; const int maxn = 500005; int sum[maxn],n,m,dis[maxn]; vector<pair<int,int> > mp[maxn]; bool vis[maxn]; void addEdge(int u,int v,int w) { mp[u].push_back(mk(v,w)); } void Solve() { memset(dis,-0x3f,sizeof(dis)); queue<int> q; dis[0] = 0; q.push(0); while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for (auto v : mp[u]) if (dis[v.first] < dis[u] + v.second) { dis[v.first] = dis[u] + v.second; if (!vis[v.first]) { vis[v.first] = true; q.push(v.first); } } } } int main() { scanf("%d%d",&n,&m); addEdge(0,1,0); // 不要忘了这里还有一个约束 for (int i = 1,x;i <= n;i ++) { scanf("%d",&x); sum[i] = sum[i - 1] + x; addEdge(i,i + 1,0); addEdge(i,i - 1,-x); } for (int i = 1,l,r,w;i <= m;i ++) { scanf("%d%d%d",&l,&r,&w); addEdge(l - 1,r,w); } Solve(); printf("%d",dis[n]); return 0; }