清北学堂2019.5.2

学堂2019.5.2"/>

清北学堂2019.5.2

Day 5（吴耀轩）

今天以图论为主

不要写奇奇怪怪的东西，那是闲得蛋疼，这很弱智，而且我喜欢被回应的感觉（比如：哦~~~~）

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　————吴耀轩

主要讲了MST（生成树），SPP（最短路径），Topsort（拓扑排序），LCA（最近公共祖先）

首先：

学好图论的基础：

• 必须意识到图论 hen dan teng
• xue hui fang qi（雾

基础知识

什么是图？ 

图（Graph【这也是为什么oier们通常设g数组的原因】）是表示物件与物件之间的关系的数学对象，是图论的基本研究对象。

一般来说，图的存储难度主要在记录边的信息，无向图的存储中，只需要将一条无向边拆成两条即可

邻接矩阵：用一个二维数组 edg[N][N] 表示
　　　　　edg【i】【j】 就对应由 i 到 j 的边信息
　　　　　edg【i】【j】可以记录 Bool，也可以记录边权
　　　　　缺点：如果有重边有时候不好处理
　　　　　空间复杂度 O(V²)

 如何存图？

1. 邻接矩阵
2. 邻接表：
3.  vector：

 MST（生成树）

给定一个联通无向图G=（V,E），E’⊂ E，G‘=（V,E‘）构成一棵树

G’就是G的一棵生成树（一个树的生成树并不唯一，其数目是一个指数级别的数量级）

给定一个 n 个点 m 条边的带权无向图，求一个生成树，使得生成树中最大边权的最小 （数据范围： n; m ≤ 106 ）

Algorithms for Minimal Spanning Tree

• Kruskal
• Prim
• Kosaraju

 这里主要介绍一下Kruskal

基础知识：并查集（冰茶几TAT）

对于百度百科的定义我也是醉了。。。

算法流程

初始化最小生成树中没有任何边。 然后由长度从小到大依次考虑每条边： 若加入最小生成树后形成了环，则不加入；否则加入。

分析

排序过程可以直接使用STL库的sort。 算法的瓶颈在于判断环上。

解法

使用并查集维护顶点之间的连接关系。 开始时没有任何点相连，即初始化并查集。 判断环时，只需判断该边的两个顶点是否原来就相连，即是否在一个集合中。 加边时，合并集合。

证明（来自OI wiki）

判环时（消圈算法qwq）【运用并查集的知识】

主要代码如下：

#include <bits/stdc++.h>using namespace std;const int maxn = 1000005;
struct edge {int u, v, w;
}edg[maxn];
int n, m, p[maxn], ans = 0;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 main()
{cin >> n >> m;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; i <= m; i++)if (merge(edg[i].u, edg[i].v))ans = max(ans, edg[i]. w);cout << ans << endl;
}

Prim几乎与Kruskal同样的道理，每次添加最近的点（本质还是最短的边）。

分析

维护一个数组记录每个点到当前的最小生成树的最短距离。每次选择其中该值最小的点加入最小生成树。

普里姆算法（Prim算法）：

图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。

大概就是这样，嗯。。。

SPP（最短路径问题）

给定一个有向图 G，询问 u 到 v 之间最短路径长度
记 d(u; v) 表示 u 到 v 的最短路径长度
为方便起见，不妨规定 u 和 v 不连通时， d(u; v) = +∞
Algorithms for Shortest Path Problem

• floyd
• Bellman-Ford

• SPFA
• Dijkstra

松弛操作

SSP 算法的本质思想就是不断进行松弛操作
d(u; v) ≤ d(u; w) + d(w; v)

Topsort（拓扑排序）

G 是一个有向无环图，则称为 DAG

DAG 不要求弱连通

DAG一定有出度为0的点

拓扑排序：

n 个点的 DAG 一定存在拓扑序列

P 是 G 的拓扑序，当且仅当
　　P 是 n 阶排列
　　若 G 中存在 u ! v 的路径，排列 P 中 u 一定出现在 v 的前面

Intuitive ideas
　　找到 DAG 中入读为 0 的点 u， u 可以放在当前 DAG 拓扑序末尾
　　将 u和与 u 有关的连边从 DAG 中删除
如何判 DAG？
　　DAG 图一定能根据上述算法找到拓扑序
时间复杂度 O(n + m)

代码大体如下：

#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()){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);}}
}

LCA（最近公共祖先）

以 r 为根的有根树上，若 a 在 r 到 x 的路径上，称 a 为 x 的祖先
若 a 是 x 和 y 共同的祖先，则称 a 是 x 和 y 的公共祖先
x 和 y 所有公共祖先中，离他们最近的称为 x 和 y 的最近公共祖先，记为 lca(x; y)

O(log n) 询问两点 LCA
Algorithms for Least Common Ancestors

• 　　树上倍增
• 　　RMQ with Euler sequence

树上倍增：

　　Initialization
　　　　　　记录 dep(x) 表示 x 到树根的距离
　　　　　　预处理 anc[x][j] 表示 x 在树上向上 2j 层的祖先
　　　　　　　　anc[x][0] = parent(x)
　　　　　　　　anc[x][j] = anc[anc[x][j - 1]][j - 1]

　　寻找 x 的 k 层祖先
　　　　写出 k 的二进制表示 k = 2e0 + 2e1 + · · · + 2et
　　　　kth(x) = anc[anc[anc[anc[... ][e3]][e2]][e1]][e0]

　　Query LCA(x,y)
　　　　将 x 和 y 调整到同一深度
　　　　　　不妨设 dep(x) > dep(y)，将 x 跳至 dep(x) - dep(y) 层祖先
　　　　若 x = y， lca(x; y) = x，下面假定 x ̸= y
　　　　枚举 j : log n ! 0
　　　　　　若 anc[x][j] ̸= anc[y][j]，将 x := anc[x][j]，将 y := anc[y][j]
　　　　此时答案就是 parent(x)

　　Property
　　　　将二者调至同一深度，显然不影响答案
　　　　下面的过程可以粗略理解为：将 x 和 y 同时向上跳相同的尽量远的高度，但保持二者不相遇，那最终的 LCA 一定是 x 和 y 的父亲
　　预处理时间复杂度 O(n log n)
　　　　anc[x][j] 中的 j 只需要 0 ! log n
　　单次询问时间复杂度 O(log n)

#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)//yu chu li
{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 depthif (u == v)    return res; //u & v meet nowfor (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.
*/

安排！！！

转载于:.html