【复习笔记】Week 2 图论

最常用的化解技巧是建虚点。 # DAY 1 跑最短路也是可以建虚点的。 ## Dijsktra Dijsktra 中也需要记录 `vis[]` 表示当前点的最短路是否已经确定，否则可能造成重复枚举同一个点周围的边，导致冗余的松弛尝试，使时间变慢。 只要出现负权边，Dijsktra 即不能使用。 注意：对于二重费用（在第一重费用最小的同时使第二重费用最小）的问题，用 SPFA 极易 TLE。这时可以采用重新重载小于号的方法。在普通的 Dijsktra 中，堆顶存放的是 `dis` 最小的点，每次取出这个点对其周围的点进行松弛；而在二重费用的题目中，则可以把这个规则进行改进，即堆顶保存 `dis` 和 `fee` 都最小的点。这样可以保证每个点从堆中取出来的时候，都取到了二重费用的最小值。 ```cpp struct node { int u; ll dis, fee; bool operator < (const node &rhs) const { if (dis != rhs.dis) return dis > rhs.dis; return fee > rhs.fee; // 二重费用的重载小于号 } node(int src_u, ll src_dis, ll src_fee) { u = src_u; dis = src_dis; fee = src_fee; } }; priority_queue<node> q; void dijsktra() { memset(dis, 0x3f, sizeof(dis)); memset(fee, 0x3f, sizeof(fee)); dis[s] = fee[s] = 0; q.push(node(s, 0, 0)); while (!q.empty()) { int u = q.top().u; q.pop(); if (vis[u]) continue; vis[u] = true; for (int i = head[u]; i; i = edge[i].next) { int v = edge[i].to; ll w = edge[i].w, c = edge[i].c; if (dis[u] + w < dis[v]) { dis[v] = dis[u] + w; fee[v] = fee[u] + c; // 更新最小费用 q.push(node(v, dis[v], fee[v])); } else if (dis[u] + w == dis[v] && fee[u] + c < fee[v]) { fee[v] = fee[u] + c; q.push(node(v, dis[v], fee[v])); // 似乎这里不再入堆也是可以的 } } } return ; } ``` ## SPFA 记得每次从队列取出点的时候，**要把 `vis[u]` 清为 `false`**，否则原地爆炸。 SPFA 判负环时，dfs - SPFA 固然是个又好又快的方法，然而我觉得通用性不如下面这种方法强：记录每个点当前最短路径上的点数 `cnt[u]`，若发现 `cnt[u] > n` 则说明出现负环。当然，这种做法的复杂度为$O(mn)$，很容易就被卡掉了；不过，大部分情况下，加上快读、`inline`、`register` 还是能够卡过。 ```cpp bool SPFA() { memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); while (!q.empty()) q.pop(); dis[1] = 0; cnt[1] = 1; // 节点数从 1 开始 q.push(1); while (!q.empty()) { int u = q.front(); vis[u] = false; q.pop(); for (int i = head[u]; i; i = edge[i].next) { int v = edge[i].to, w = edge[i].w; if (dis[u] + w < dis[v]) { dis[v] = dis[u] + w; cnt[v] = cnt[u] + 1; if (cnt[v] > n) return true; if (!vis[v]) { vis[v] = true; q.push(v); } } } } return false; } ``` ## 差分约束 差分约束系统推出的条件，是跑完 SPFA 之后整张图所满足的。所以，等价条件 `dis[u] + w <= dis[v]` 该跑 **最长路**，`dis[u] + w >= dis[v]` 该跑 **最短路**。 最长路型差分约束系统的条件转换： 1. $a-b\geq c \Leftrightarrow$ `dis[b] + c <= dis[a]` $\Leftrightarrow$ `build_edge(b, a, c)` 2. $a-b\leq c \Leftrightarrow$ `dis[a] - c <= dis[b]` $\Leftrightarrow$ `build_edge(a, b, -c)` 3. $a=b\Leftrightarrow$ `build_edge(a, b, 0), build_edge(b, a, 0)` 建完所有关系边之后，为了获取整张图是否存在负环的信息，一种方法是一个一个连通块地跑；另一种方法是**新建虚点** `0` 并从虚点向所有点连一条长度为$0$的有向边，最后 `SPFA(0)` 即可。 ## 最短路树 **等长路径字典序最小** 的最短路树的生成方式：维护一个 `conn[]` 表示当前点是否被连入最短路树。按编号从小到大枚举节点$u$，这样就能保证是按照字典序从小到大枚举；寻找$u$所指向的所有结点$v$，如果 `conn[v] == false` 并且这条边满足最短路树的性质，则证明当前这条边可以连入最短路树，那么直接在 `edge2` 上建边即可。 ```cpp // https://www.luogu.org/problem/P5201 void build_tree() { conn[1] = true; for (int u = 1; u <= n; u++) for (int i = head1[u]; i; i = edge1[i].next) { int v = edge1[i].to, w = edge1[i].w; if (conn[v]) continue; if (dis[u] + w == dis[v]) { conn[v] = true; build_edge(edge2, head2, id2, u, v, 1); build_edge(edge2, head2, id2, v, u, 1); } } return ; } ``` # DAY 2 ## 缩点 缩完点建新图的时候，一定要记住 **新图里点 $u$ 的编号是 `scc[u]`**，千万不要逮着原图的点建图（多次死亡）。 缩点的时候要考虑到 **两点环** 的可能，所以不能判断$v$是否为父亲，而应该考虑$v$是否在栈内。 ```cpp void tarjan(int u) { dfn[u] = low[u] = ++cnt; s[++top] = u, ins[u] = true; for (register int i = h1[u]; i; i = e1[i].next) { int v = e1[i].to; if (!dfn[v]) { tarjan(v); low[u] = my_min(low[u], low[v]); } else if (ins[v]) low[u] = my_min(low[u], dfn[v]); } if (dfn[u] == low[u]) { scc_cnt++; int v; do { v = s[top--]; ins[v] = false; scc[v] = scc_cnt; p2[scc_cnt] += p[v]; } while (v != u); } } ``` ## 割点 割点需要特判 dfs 树的树根（也就是代码中的 `fa` ），具体为：若 `fa` 在 dfs 树中的儿子个数$\geq2$，则 `fa` 也是一个割点。 而对于一般的点$u$，只有在没有搜过$u$的情况下才会考察$u$是否为一个割点；不然就用 `dfn[v]` 更新 `low[u]` 即可。 ```cpp void tarjan(int u, int fa) { dfn[u] = low[u] = ++dfscnt; int cnt = 0; for (int i = head[u]; i; i = edge[i].next) { int v = edge[i].to; if (!dfn[v]) { tarjan(v, fa); // 注意是把 fa 下传 low[u] = min(low[u], low[v]); if (u != fa && low[v] >= dfn[u]) cut[u] = true; // 普通的点 if (u == fa) cnt++; // 特判 fa 的情况 } else low[u] = min(low[u], dfn[v]); // 这里不需要再带上判割点的语句 } if (u == fa && cnt > 1) cut[u] = true; return ; } ``` ## 桥 在基环树上，断掉所有的桥，剩下的边就是环上的边。 tarjan 找桥的过程中，需要判断反向边。 ```cpp void tarjan(int u, int pre) { dfn[u] = low[u] = ++dfscnt; for (int i = head[u]; i; i = edge[i].next) { if (i == (pre ^ 1)) continue; int v = edge[i].to; if (!dfn[v]) { tarjan(v, i); if (low[v] > dfn[u]) cut[i] = true; low[u] = min(low[u], low[v]); } else low[u] = min(low[u], dfn[v]); } return ; } ``` # DAY 3 ## 欧拉回路 半欧拉回路的起点必须为奇数度数点，而欧拉图的起点可以任意取。注意：有可能需要倒序记录路径。 ```cpp void hierholzer(int u) { for (int v = 'A'; v <= 'z'; v++) if (G[u][v]) { G[u][v] = G[v][u] = 0; hierholzer(v); } res[tail--] = u; return ; } ``` ## 最小生成树 ### Kruskal Kruskal 的复杂度由边数$m$决定，因此太稠密的图不能跑 Kruskal（然而这种情况并不多见）。 ### Prim Prim 的思路类似 Dijsktra，并且主函数也只有一小点区别。也就是说，维护一个 `dis[u]` 表示点$u$到当前生成树的最短距离；每次找出不在生成树中的 `dis[]` 最小的点，并连入生成树中。当然，由于思路和 Dijsktra 相似，Prim 也是可以加堆优化的。不加堆优化的 Prim 在超级稠密图中的性能优于 Kruskal。 ```cpp // Prim 的邻接矩阵写法 void prim() { memset(dis, 0x3f, sizeof(dis)); for (int i = 1; i <= n; i++) dis[i] = min(dis[i], G[1][i]); int u = 1; while (++tot < n) { vis[u] = true; int minn = 0x3f3f3f3f; for (int i = 1; i <= n; i++) if (!vis[i] && dis[i] < minn) { u = i; minn = dis[i]; } ans += minn; for (int i = 1; i <= n; i++) if (!vis[i] && G[u][i] < dis[i]) dis[i] = G[u][i]; } return ; } ``` ## 最小生成森林 最小生成森林可以看作所有树的根都连到超级根上的最小生成树，所以从超级根向每一个可以作为树根的点连一条边，即可获得最小生成森林。这里又用到了 **建虚点** 的方法。当然，最小生成森林也可以简单地用并查集维护，只需要统计 `fa[i] == i` 的点即可。 事实上，只要涉及到 **一条边减少一个联通块** 的问题，极有可能与最小生成树 / 最小生成森林相关。 # DAY 4 ## 二分图染色 只要一个图中没有奇环，那么这个图就是一个二分图。通常可以使用黑白染色法把一个图转化为二分图。二分图的核心在于 **如何建图**。 二分图的题目中，点和边的实际意义是很灵活的，比如可以把坐标系上的点$P$当成边，从$x_P$向$y_P$连一条边；也可以把一个网格图黑白染色后两两连边，每条边代表将这条边所连的两个点放在同一个矩形里。 不过，因为二分图中的点只有 `x[]` 和 `y[]` 两列，所以对于二维网格图上的点，需要先把点映射到一个数字上，然后才能放到点列当中。 ## 二分图匹配 **匈牙利算法** 的本质是寻找增广路（也就是进行匹配协商）。复杂度为$O(nm)$。由于 `vis[u]` 记录的是点$u$是否在当前增广路上，所以 **每次找增广路后都需要把 `vis[]` 清零**。 ```cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 1e3 + 10; int cx[MAXN], cy[MAXN], G[MAXN][MAXN]; bool vis[MAXN]; int n, m, e, ans = 0; bool hungary(int x) { for (int y = 1; y <= m; y++) if (!vis[y] && G[x][y]) { vis[y] = true; // 标记当前点已经在增广路上 if (!cy[y] || hungary(cy[y])) { // 若还能找到增广路 / 进行协商 cx[x] = y; cy[y] = x; return true; } } return false; } int main() { memset(cx, 0, sizeof(cx)); memset(cy, 0, sizeof(cy)); // 必须初始化 scanf("%d %d %d", &n, &m, &e); for (int u, v; e; e--) { scanf("%d %d", &u, &v); if (u > n || v > m) continue; G[u][v] = 1; } for (int i = 1; i <= n; i++) { memset(vis, 0, sizeof(vis)); // 每次都必须 memset() ans += hungary(i); } // 从每个点尝试寻找增广路，若找到增广路则 ans++ printf("%d", ans); return 0; } ``` 当然，每次对 `vis[]` 进行一次 `memset()` 比较慢。为了加速，可以把 `vis[]` 改成时间戳，也就是下面的写法： ```cpp bool hungary(int x) { for (int y = 1; y <= n; y++) if (G[x][y] && vis[y] != cur) { vis[y] = cur; if (!cy[y] || hungary(cy[y])) { cx[x] = y; cy[y] = x; return true; } } return false; } int match() { memset(cx, 0, sizeof(cx)); memset(cy, 0, sizeof(cy)); memset(vis, 0, sizeof(vis)); cur = 1; int res = 0; for (int i = 1; i <= n; i++, cur++) res += hungary(i); return res; } ``` ## 二分图的一些性质 ### 最小点覆盖 **最小点覆盖：** 选取最少的一些点使得所有边都与这些点相连。 二分图中，**最小点覆盖$=$最大匹配**。 **例题：** 有一些障碍物位于一张$n\times n$的网格图上，每次可以消除一行或者一列上的所有障碍物，求最少需要消除多少次才能清除所有障碍物。 **分析：** 对于每个障碍物$(x,y)$，从$x$向$y$连一条边，每条边代表一个障碍物。那么可以看出，只要选出一个点$x$，与$x$相连的所有边（即横坐标为$x$的所有障碍物）都会被覆盖；而题目要求所有边都被覆盖。所以，问题就转化为了最小点覆盖。 ```cpp // http://poj.org/problem?id=3041 #include <iostream> #include <stdio.h> #include <cstring> using namespace std; const int MAXN = 510; int n, k; int G[MAXN][MAXN], cx[MAXN], cy[MAXN]; bool vis[MAXN]; bool hungary(int x) { for (int y = 1; y <= n; y++) if (G[x][y] && !vis[y]) { vis[y] = true; if (!cy[y] || hungary(cy[y])) { cx[x] = y; cy[y] = x; return true; } } return false; } int match() { int res = 0; for (int i = 1; i <= n; i++) { memset(vis, 0, sizeof(vis)); res += hungary(i); } return res; } int main() { memset(cx, 0, sizeof(cx)); memset(cy, 0, sizeof(cy)); scanf("%d %d", &n, &k); for (int x, y; k; k--) { scanf("%d %d", &x, &y); G[x][y] = 1; } printf("%d", match()); return 0; } ``` ### 最小边覆盖 **最小边覆盖：** 选取最少的一些边使得所有点都与这些边相连。 二分图中，**最小边覆盖$=$总点数$-$最大匹配数**。 **例题：** 有一个网格，上面有一些可选点，每次可以覆盖一个$1\times2$大小的矩形，求出把所有点都覆盖住的最小覆盖次数。 **分析：** 考虑如何建图。先把图黑白染色，对于每个黑色可选点，向上下左右的白色可选点连边。对于任意一条边，选取这条边代表这条边所连的两点在同一矩形内；而题目要求所有点都被覆盖。所以，问题就转化为了最小边覆盖。 ```cpp // poj.org/problem?id=3020 #include <iostream> #include <stdio.h> #include <cstring> using namespace std; const int MAXN = 3e3 + 10; const int dx[] = {-1, 1, 0, 0}; const int dy[] = {0, 0, -1, 1}; int G[MAXN][MAXN]; int T, h, w, n; char s[MAXN][MAXN]; int cx[MAXN], cy[MAXN]; bool vis[MAXN]; bool accept(int x, int y) { return x > 0 && x <= h && y > 0 && y <= w; } int getid(int x, int y) { return (x - 1) * w + y; } // 需要把点映射到一个数上，方便连边 bool hungary(int x) { for (int y = 1; y <= n; y++) if (!vis[y] && G[x][y]) { vis[y] = true; if (!cy[y] || hungary(cy[y])) { cx[x] = y; cy[y] = x; return true; } } return false; } int match() { int res = 0; for (int i = 1; i <= n; i++) { memset(vis, 0, sizeof(vis)); res += hungary(i); } return res; } int init() { memset(G, 0, sizeof(G)); memset(cx, 0, sizeof(cx)); memset(cy, 0, sizeof(cy)); int res = 0; for (int x = 1; x <= h; x++) for (int y = 1; y <= w; y++) if (s[x][y] == '*') { res++; if ((x + y) & 1) continue; for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (!accept(nx, ny)) continue; if (s[nx][ny] == '*') G[getid(x, y)][getid(nx, ny)] = 1; } } return res; } int main() { scanf("%d", &T); while (T-- && scanf("%d %d", &h, &w)) { for (int i = 1; i <= h; i++) scanf("%s", s[i] + 1); n = h * w; int tot = init(); printf("%d\n", tot - match()); } return 0; } ``` # DAY 5 ## 树链剖分 剖完以后$u,v$的跳转非常易错，需要判断的是 **`top[u]` 和 `top[v]` 的深度关系** 而不是 `u` 和 `v`。 ```cpp void Update(int u, int v, ll c) { c %= p; while (top[u] != top[v]) { if (dep[top[u]] < dep[top[v]]) swap(u, v); // 注意是 dep[top[u]] < dep[top[v]] edit_tree(1, dfn[top[u]], dfn[u], c); u = fa[top[u]]; } if (dep[u] > dep[v]) swap(u, v); edit_tree(1, dfn[u], dfn[v], c); return ; } ``` # DAY 6 ## 树上问题 一般树上问题的解决思路是考虑子树，然后考虑子树能够上传些什么给父节点。比如树上链问题，单独考虑一棵子树的话，子树内的链可以分为三种情况： 1. 链在子树内，且不经过根节点； 2. 链在子树内，且经过根节点； 3. 链不全在子树内。 分别考虑每种情况对应的处理方法，就可以分治地解决一些树上问题（2018 D1T3）。 ## 树的重心 定义：选取树上的一个点作为树根，使得最大子树最小，则这个点为树的重心。 求法：以任意点为根跑一遍 dfs，然后统计 `max(size[v], n - size[u] - 1)` 最小的点，即可获得重心。 ### 一些性质 树中所有点到某节点的距离和中，到重心的距离和是最小的；若有两个重心，则其距离和相等； 把两个树通过一条边相连得到一棵新树，那么新树的重心在连接原来两个树的重心的路径上； 添加或删除一个叶子，那么树的重心最多只移动一个点。 ## 树的直径 定义：树上任意两点的最长距离为树的直径。 直径共有两种求法，都是$O(n)$。 贪心求法：正反两遍 dfs，第一次以任意节点为根 dfs 到最远的点$u$，第二次从$u$开始 dfs 到最远的点$v$，则$u\rightarrow v$即树的直径。 ```cpp int dia = 0, p; void dfs(int u, int fa, int pre) { if (pre > dia) { dia = pre; p = u; } for (int i = head[u]; i; i = edge[i].next) { int v = edge[i].to, w = edge[i].w; if (v == fa) continue; dfs(v, u, pre + w); } return ; } inline void prework() { dfs2(1, 1, 0); dfs2(p, p, 0); return ; } ``` 动规求法（适用于所有情况）：$f[u]$表示从$u$开始向下能够延伸的最长链长度，每次对于一个儿子$v$，先用$f[u]+f[v]+dis[u\rightarrow v]$更新答案，然后用$f[v]+dis[u\rightarrow v]$更新$f[u]$。这样可以保证不会重复计算同一条链。 ### 一些性质 设两棵树的直径分别是$(u_1\rightarrow v_1), (u_2\rightarrow v_2)$，则用一条边将两棵树相连，新的直径$(u\rightarrow v)$一定满足$u,v\in \{u_1,u_2,v_1,v_2\}$； 若给树加一个节点，新的直径最多改变一个端点。 # 总结 再次强调图论的经典处理方法：建反图，建虚点，边排序。 在这些知识点中，有关树的部分很可能是和树形 dp 结合考察，因此要向两个方向试探，不能局限思维。点和边的意义也不能局限于常见的套路，比如二分图中，边的意义甚至是点。涉及到树上查询的问题，一般是用树上倍增实现；如果用树链剖分 + 线段树则时间复杂度会多出一个$logn$，这种情况下就需要用 ST 表使得单次查询复杂度达到$O(1)$。 总而言之，图论的难点就在于建模。 --- # $\footnotesize\text{Weathering With You}$    重拾那份爱的勇气，纵使世界就这样疯狂下去，我毫不在意 跨越无尽黑夜，逃离阳光无法企及之地 无论是晴是雨，不管多远距离，也一定要去见你 当大地失去了重力，千年一遇的奇迹 我和你，十指相扣，翱翔天际 「呐，现在开始就要放晴了哦。」 ——希望百分百晴天女孩的祈祷，也能驱散你心中的阴云。 $\large\texttt{by NCC-79601}$ $\footnotesize\text{Weathering With You}$