内容提要
图论：
dijkstra
拓扑排序
最近公共祖先
Dijkstra
无负权的图能不能在 SSP 上更高效？
- d(u) 被更新成真实值之前， u 出边的松弛操作都无意义
- 前面的算法中不知道谁是真实值，但是这里没有负权，所以我们每次用最小的边更新其他的
Intuitive ideas
- 维护 Queue，表示 Queue 里面点的出边都被松弛过了
- 找出不在 Queue 中的， d(u) 最小的 u
- 松弛所有 u 的出边
- 将 u 加入 Queue后，在 Queue 中的点 d 不会再更新
那么问题来了，怎么找到不在 Queue 中 d(u) 最小的 u？？？
暴力扫描所有点？
代码：
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; const int inf = 1 << 29; struct edge{ int u, v, w; }; vector<edge> edg[N]; int d[N], n, m, S; bool relaxed[N];//一个点在不在队列里 void add(int u, int v, int w) { edg[u].push_back((edge){u, v, w}); } int main() { cin >> n >> m >> S; for (int i = 1; i <= n; i++) d[i] = inf; for (int u, v, w, i = 1; i <= m; i++) cin >> u >> v >> w, add(u, v, w); d[S] = 0; for (int i = 1; i <= n; i++) { int u = 1; while (relaxed[u]) ++u;//找到1~n中第一个不在队列中的 for (int j = 1; j <= n; j++)//找到不在队列当中的最小的u if (!relaxed[j] && d[j] < d[u]) u = j; //find a node u not relaxed yet with least d(u) relaxed[u] = true;//把它标记为在队列中 for (int e = 0; e < edg[u].size(); e++) { int v = edg[u][e].v, w = edg[u][e].w; d[v] = min(d[v], d[u] + w);//枚举松弛 } } for (int i = 1; i <= n; i++) cout << d[i] << endl; }
时间复杂度 O(n^2 + m)，有点高吖
可以用小根堆 PQueue 维护
一旦 d(u) 被更新，就将 u 插入 PQueue，关键字为 d(u)
如何删除 PQueue 中以未更新前的 d(u) 为关键字的节点？
不需要删除！因为以更新后的 d(u) 为关键字的节点会一定先出堆，用Bool 数组记录每个点的出边是否松弛过了，当 PQueue 的堆顶 u 在Bool 数组中被标记后，不用再重复松弛
代码：
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; const int inf = 1 << 29; struct edge{ int u, v, w; }; vector<edge> edg[N]; int d[N], n, m, S; bool relaxed[N]; struct Qnode { int u, du; bool operator<(const Qnode &v) const {return v.du < du;}//当v的优先级比现在的更小的时候，把它放在上面 }; priority_queue<Qnode> PQueue; void add(int u, int v, int w) { edg[u].push_back((edge){u, v, w}); } int main() { cin >> n >> m >> S; for (int i = 1; i <= n; i++) d[i] = inf; for (int u, v, w, i = 1; i <= m; i++) cin >> u >> v >> w, add(u, v, w); d[S] = 0; PQueue.push((Qnode){S, 0}); while (!PQueue.empty()) { int u = PQueue.top().u; PQueue.pop(); if (relaxed[u]) continue;//如果所有出边都被松弛过就跳出 //if edges staring from u are already relaxed, no need to relax again. relaxed[u] = true; for (int e = 0; e < edg[u].size(); e++) { int v = edg[u][e].v, w = edg[u][e].w; if (d[v] > d[u] + w) { d[v] = d[u] + w; PQueue.push((Qnode){v, d[v]}); //if d(v) is updated, push v into PQueue } } } for (int i = 1; i <= n; i++) cout << d[i] << endl; }
一些 PQueue 的细节
c++ 模板库中已经有 priority_queue 实现好了堆
加入一个元素 p.push(a)
访问堆 p 的顶 p.top()
弹出堆 p 的顶 p.pop()
判断 p 是否为空 p.empty()
如何定义堆中大小比较顺序：可以参考示例代码的写法
Time Complexity
每条边只会进行一次松弛
PQueue 压入 u，意味着 d(u) 被更新
时间复杂度 O(m + mlog n)
DAG
G 是一个有向无环图，则称为 DAG
DAG 不要求弱连通
拓扑排序
n 个点的 DAG 一定存在拓扑序列
P 是 G 的拓扑序，当且仅当
- P 是 n 阶排列
- 若 G 中存在 u --> v 的路径，排列 P 中 u 一定出现在 v 的前
显然拓扑序也是不一定唯一的，并且数量是指数（至少也是阶乘）级别的
证明任何一个DAG一定有拓扑序
证明：
1.任何一个DAG一定有出度为0的点
2.出度为0的点放在拓扑序的最后一定没有问题，然后把这个点和他的边删除
3.不断操作，最后得到拓扑序
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; const int inf = 1 << 29; struct edge{ int u, v; }; vector<edge> edg[N]; int n, m, outdeg[N], ans[N]; queue<int> Queue; void add(int u, int v) { edg[u].push_back((edge){u, v}); } int main() { cin >> n >> m; for (int u, v, i = 1; i <= m; i++) cin >> u >> v, add(v, u), outdeg[u]++;//出度++ for (int i = 1; i <= n; i++) if (outdeg[i] == 0) Queue.push(i); for (int i = 1; i <= n; i++) { if (Queue.empty())//如果空了，说明肯定不是dag {printf("Not DAG"); return 0;} int u = Queue.front(); Queue.pop(); ans[n - i + 1] = u; for (int e = 0; e < edg[u].size(); e++) { int v = edg[u][e].v; if (--outdeg[v] == 0) Queue.push(v); }//把指向u的点删掉，出度--，然后判断出度是否为0 } }
如何求DAG的拓扑排序数量？
无法做到
哈哈哈~
最近公共祖先
以 r 为根的有根树上，若 a 在 r 到 x 的路径上，称 a 为 x 的祖先
若 a 是 x 和 y 共同的祖先，则称 a 是 x 和 y 的公共祖先
x 和 y 所有公共祖先中，离他们最近的称为 x 和 y 的最近公共祖
先，记为 lca(x,y)
先来看一个最暴力的Floyd写法（O(n^3)）
#include <bits/stdc++.h> using namespace std; const int maxn = 105; const int inf = 1 << 29; int dis[maxn][maxn], n, m, Q; int main() { cin >> n >> m >> Q; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (i != j) dis[i][j] = inf; for (int i = 1, u, v, w; i <= m; i++) cin >> u >> v >> w, dis[u][v] = min(dis[u][v], w), dis[v][u] = min(dis[v][u], w); for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dis[i][j] = min(dis[i][j], max(dis[i][k], dis[k][j])); for (int u, v, i = 1; i <= Q; i++) cin >> u >> v, cout << dis[u][v] << endl; } /*Problem statement Given a graph G containing n nodes and m bidirectional edges. The weight of a path p0->p1->p2->...->pt is the maximum weight of edges on the path. There are Q queries given (u, v), output the minimum weight of paths from u to v. Guarantee between any nodes u & v , there is at least one path from u to v. */
显然非常容易tle
还有其他方法吗?
树上倍增！
O(log n) 询问两点 LCA
Algorithms for Least Common Ancestors
RMQ with Euler sequence
Initialization
记录 dep(x) 表示 x 到树根的距离
预处理 anc[x][j] 表示 x 在树上向上 2^j 层的祖先
anc[x][0] = parent(x)
anc[x][j] = anc[anc[x][j − 1]][j − 1]
寻找 x 的 k 层祖先
写出 k 的二进制表示 k = 2^e0 + 2^e1 + · · · + 2^et
kth(x) = anc[anc[anc[anc[......][e3]][e2]][e1]][e0]
代码：
#include<bits/stdc++.h> using namespace std; long long read(){ long long ans=0; char last=' ',ch=getchar(); while(ch<'0' || ch>'9')last=ch,ch=getchar(); while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar(); if(last=='-')ans=-ans; return ans; } const int maxn=500010; int n,m,s,anc[maxn][21],dep[maxn]; struct edge { int u,v; }edg[maxn]; vector<edge> adj[maxn]; void dfs(int u) { for(int j=1;j<20;j++) anc[u][j]=anc[anc[u][j-1]][j-1]; for(int i=0;i<adj[u].size();i++) { int v=adj[u][i].v; if(v!=anc[u][0]) dep[v]=dep[u]+1,anc[v][0]=u,dfs(v); } } int solve(int u,int v) { if(dep[u]<dep[v]) swap(u,v); for(int d=dep[u]-dep[v],j=0;d;d>>=1,j++) if(d&1) u=anc[u][j]; if(u==v) return u; for(int j=19;j>=0;j--) if(anc[u][j]!=anc[v][j]) u=anc[u][j],v=anc[v][j]; return anc[u][0]; } int main() { n=read(),m=read(),s=read(); for(int u,v,i=1;i<n;i++) { u=read(),v=read(); edg[i]=(edge){u,v}; } for (int i = 1; i <= m; i++) { int u = edg[i].u, v = edg[i].v; adj[u].push_back(edg[i]), adj[v].push_back((edge){v, u}); } dfs(s); for(int u,v,i=1;i<=m;i++) { u=read(),v=read(); printf("%d ",solve(u,v)); } }
对应的就是洛谷P3379
(洛谷的题怎么都这么喜欢卡常呢QwQ
Exercise
给定 n 个点的带边权树， Q 次询问，每次给定 x 和 y，询问 x 到 y的距离。
数据范围 n; Q ≤ 10^5
Solution
以 1 为根， DFS 时记录 len(x) 表示 x 到根的距离
设 t = lca(x; y)， x --> y 的路径可以拆程 x --> t 和 t --> y 两段
答案就是 len(x) + len(y) − 2len(t)
Exercise
给定 n 个点 m 条边带边权的无向连通图， Q 次询问，每次给定 x和 y，询问 x 到 y 的所有路径中最大边权的最小值。
数据范围 n; Q ≤ 10^5
Solution
x --> y 的答案一定在 MST 上
在 MST 上询问 x --> y 上的最大边权
倍增时多记一项 maxw[x][j]，表示 x --> anc[x][j] 上的最大边权
maxw[x][j] = max{maxw[x][j − 1]; maxw[anc[x][j − 1]][j − 1]}
dijkstra加倍增做法：
#include <bits/stdc++.h> using namespace std; const int maxn = 1000005; struct edge { int u, v, w; }edg[maxn]; int n, m, p[maxn], Q, dep[maxn]; vector<edge> adj[maxn]; // edges in MST bool cmp(edge a, edge b) {return a.w < b.w;} int findp(int t) {return p[t] ? p[t] = findp(p[t]) : t;} bool merge(int u, int v) { u = findp(u); v = findp(v); if (u == v) return false; p[u] = v; return true; } int anc[maxn][20], maxw[maxn][20]; void dfs(int u) { for (int j = 1; j < 20; j++) anc[u][j] = anc[anc[u][j - 1]][j - 1], maxw[u][j] = max(maxw[u][j - 1], maxw[anc[u][j - 1]][j - 1]); for (unsigned i = 0; i < adj[u].size(); ++i) { int v = adj[u][i].v, w = adj[u][i].w; if (v != anc[u][0]) dep[v] = dep[u] + 1, anc[v][0] = u, maxw[v][0] = w, dfs(v); } } int solve(int u, int v) { int res = 0; if (dep[u] < dep[v]) swap(u, v); for (int d = dep[u] - dep[v], j = 0; d ; d >>= 1, ++j) if (d & 1) res = max(res, maxw[u][j]), u = anc[u][j]; //adjust u & v to the same depth if (u == v) return res; //u & v meet now for (int j = 19; j >= 0; j--) if (anc[u][j] != anc[v][j]) // if anc[u][j] & anc[v][j] dont meet together, then jump u & v res = max(res, maxw[u][j]), res = max(res, maxw[v][j]), u = anc[u][j], v = anc[v][j]; //now u & v 's lca must be their parent now, in an easy word, it's anc[u][0] or anc[v][0] res = max(res, maxw[u][0]); res = max(res, maxw[v][0]); u = anc[u][0]; v = anc[v][0]; return res; } int main() { cin >> n >> m >> Q; for (int i = 1, u, v, w; i <= m; i++) cin >> u >> v >> w, edg[i] = (edge){u, v, w}; sort(edg + 1, edg + m + 1, cmp); for (int i = 1, u, v; i <= m; i++) if (merge(u = edg[i].u, v = edg[i].v)) adj[u].push_back(edg[i]), adj[v].push_back((edge){v, u, edg[i].w}); dfs(1); for (int u, v, i = 1; i <= Q; i++) cin >> u >> v, cout << solve(u, v) << endl; } /*Problem statement Given a graph G containing n nodes and m bidirectional edges. The weight of a path p0->p1->p2->...->pt is the maximum weight of edges on the path. There are Q queries given (u, v), output the minimum weight of paths from u to v. Guarantee between any nodes u & v , there is at least one path from u to v. */