集训大纲
- Week1:
- 图论：拓扑排序、欧拉回路、二分图、最小生成树
- 数据结构：并查集、堆、单调队列
- week2：
- 图论：连通性
- 数据结构：线段树
图论
拓扑排序
将 DAG 上的点以关联性进行排序，得到一个有关联的枚举顺序。
有了这种特别的枚举顺序，使得在 DAG 上 DP 的转移过程更加合理且有序。
所以，DAG \(\to\) DP \(\to\) 拓扑排序。
另类排序顺序
Eg. 菜肴制作
要求在满足拓扑序的条件下，小编号的尽可能靠前。
小编号靠前 = 大编号靠后
不妨倒序考虑，先将大编号的向前放，最后倒序输出。
那么由于要让原本在后的在前，相当于反转拓扑序，所以建反图，然后满足大编号向前，即字典序越大越好，所以将队列改成大根堆即可。
数量关系建图
Eg. 数列恢复
有一个长度为 \(n\) 的整数数列 。
定义 \(s_{i, j} = \sum_{k = i}^j a_k\) 。
你现在只知道所有 \(s_{i, j}\) 的符号，请恢复一个合法的数列，或指出不存在这样的数列。
\(s_{i, j}\) 表示的是区间和，那么转化一下，可以用前缀和表示区间和 \(sum_j - sum_{i - 1} = s_{i, j}\)。
那么已知 \(s_{i, j}\) 符号，\(sum_j\) 和 \(sum_{i - 1}\) 的大小关系也就知道了。
通过大小关系建图，\(e_{u, v}\) 表示 \(sum_u < sum_v\)，然后拓扑排序构造 \(sum_v = \max(sum_u + 1)\) 即可。
那么 \(s_{i, j} = 0\) 呢？
既然 \(s_{i, j} = 0\) 表示 \(sum_{i - 1} = sum_j\) 那么不妨改变一下节点的定义：\(u\) 表示所有值为 \(sum_u\) 的点。当 \(s_{i, j} = 0\) 的时候 \(sum_{i - 1}\) 和 \(sum_j\) 等价，直接将其合并（用并查集维护起来），最后取值时直接取集合代表的值即可。
最后每个 \(a_i = sum_i - sum_{i - 1}\)。
丑陋代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 10;
int n;
int f[N];
char s[N][N];
vector<int> G[N], g[N];
int find (int x) {
if (x == f[x]) return x;
return f[x] = find(f[x]);
}
int in[N], a[N];
map<int, int> mp;
signed main() {
ios::sync_with_stdio(0);
while (cin >> n) {
mp.clear();
for (int i = 0; i <= n; i ++) f[i] = i, G[i].clear(), g[i].clear(), a[i] = 0, in[i] = 0;
for (int i = 1; i <= n; i ++) {
for (int j = i; j <= n; j ++) {
cin >> s[i][j];
if (s[i][j] == '+') {
G[i - 1].push_back(j);
} else if (s[i][j] == '-') {
G[j].push_back(i - 1);
} else {
f[find(j)] = find(i - 1);
}
}
}
for (int i = 0; i <= n; i ++) {
for (auto u : G[i]) {
g[find(i)].push_back(find(u)), in[find(u)] ++;
}
}
queue<int> q;
int tot = 0, idx = 0;
for (int i = 0; i <= n; i ++) {
if (!mp[find(i)]) {
if (!in[find(i)]) q.push(find(i));
idx ++;
mp[find(i)] = 1;
}
}
while (!q.empty()) {
int u = q.front();
q.pop(), tot ++;
for (auto v : g[u]) {
a[v] = max(a[v], a[u] + 1);
if(!(-- in[v])) {
q.push(v);
}
}
}
if(tot != idx) cout << "NO\n";
else {
cout << "YES\n";
for (int i = 1; i <= n; i ++) {
cout << a[find(i)] - a[find(i - 1 )] << ' ';
}
cout << endl;
}
}
return 0;
}
说实话，如果不知道算法是拓扑排序，这道题我绝对不知道要往图论方向想。
欧拉回路
这个知识点还是很陌生的，毕竟 GG 只给我们做了板题
定义
一条经过了图 \(G\) 所有的边仅一次的路径，即为欧拉路径（一笔画）。
特别的，当起点与终点相同时，称为欧拉回路。
判别
大前提：该图弱联通（有向）或联通（无向）
定义：\(in_u,out_u\) 分别表示有向图中一个点的入度和出度，\(d_u\) 表示一个无向图中的一个点的度数。
- 有向图
当且仅当所有点 \(in_u = out_u\) 时，该有向图存在欧拉回路。
当且仅当除起点和终点以外的点 \(in_u = out_u\)，且 \(in_{起点} = out_{起点} - 1，in_{终点} = out_{终点} + 1\)，该有向图存在欧拉路径。 - 无向图
当且仅当该图仅有 \(0\) 个奇点，该图存在欧拉回路。
当且仅当该图仅有 \(2\) 个奇点，该图存在欧拉路径。
寻找
从奇点（欧拉路径）或任意一点（欧拉回路）开始 DFS，每次经过一条边就将其删去（保证每一条边仅经过一次），然后以后序输出。
对于欧拉回路，显然这样输出实际上即为遍历顺序，并且每次回溯前一定已经将该点可达的所有环全部走过；但对于欧拉路径，遍历过程中可能会在走一部分环后走到终点并且无法继续，此时会出现回溯并重新遍历路径上尚未遍历的环，也就是方案不能仅仅按照遍历顺序。因此这时按照后序输出，就相当于首先保证遍历所有环然后再考虑剩余的路径，从而保证了正确性。
实现技巧：
- 删边：可以使用链前，由于每次存边时，正边和反边的编号 \(\oplus 1\) 即可得到另一边的编号，所以每次删除 \(i\) 和 \(i \oplus 1\) 号边即可。
考察方向：
建模
-
宝石装箱
有 \(4n\) 颗宝石，价值分别为 \(1 \sim 4n\) 。
宝石的颜色共有 \(n\) 种，每种颜色恰好有 \(4\) 颗宝石。
现在要将宝石装进两个箱子，满足以下两个条件：- 两个箱子的宝石总价值相等；
- 每个箱子每种颜色恰有 \(2\) 颗宝石。
请你设计一种划分方案，数据保证一定存在符合条件的划分方案。
条件 1 很好满足，每次选取 \((i, 4n - i)\) 的宝石放入一个箱子中，\((i + 1, 4n - i - 1)\) 放入另一个箱子中即可。
现在关键在于要满足条件 2。
对于每组 \((c_i, c_{4n - i})\) 将其视作边，该图一定存在欧拉回路：每种颜色必定度数为 \(4\)。又因为刚才满足条件 \(1\) 时的奇偶分组，所以求出该图的欧拉回路之后，奇偶间隔取边所对应的 \((i, 4n - i)\) 即可。
构造
-
最少路径覆盖问题
要求：简单路径，每条路径不能重复
由于欧拉路径是保证不重复经过每一条边的，所以可以尝试用欧拉路径去覆盖这张图。
若该图没有奇点，\(1\) 条欧拉路径即可覆盖完整个图。
若该图奇点数 \(\ge 2\)，那么该图会长这样：
人类智慧
由于握手定理，奇点数量为偶数个。
若要使其被多条欧拉路径所覆盖，可以先将两两奇点连边，使得该图为欧拉图，然后找出该图的欧拉路径，删除其中的虚边，即为覆盖完该图需要的欧拉路径条数。
所以最后答案即为 : \(cnt / 2\)。
NKOJ P8436 守卫王国
#include <vector> #include <iostream> #include <stack> #include <cstring> using namespace std; #define endl '\n' const int N = 5e5 + 10; int n, m; struct edge { int to, nxt, id; }e[N]; int h[N], idx, tmp; void add (int u, int v, int id) { e[idx] = edge{v, h[u], id}, h[u] = idx, idx ++; e[idx] = edge{u, h[v], - id}, h[v] = idx, idx ++; } vector<int> col[N]; int bel[N], tot; int vis[N]; void findltk (int u) { col[tot].push_back(u), bel[u] = tot; for (int i = h[u]; ~i ; i = e[i].nxt) { if(!bel[e[i].to]) findltk(e[i].to); } } int d[N]; bool mark[N]; stack<int> ans; void dfs (int u) { for (int i = h[u]; ~i; i = e[i].nxt) { if(mark[i]) continue; h[u] = e[i].nxt; mark[i] = mark[i ^ 1] = 1; dfs(e[i].to); ans.push(e[i].id); } } signed main () { ios::sync_with_stdio(0); cin >> n >> m; memset(h, -1, sizeof h); while(m --) { int u, v; cin >> u >> v; add(u, v, ++ tmp), d[u] ++, d[v] ++; } for (int i = 1; i <= n; i ++) { if(! bel[i]) ++ tot, findltk(i); } int num = 0; for (int i = 1; i <= tot; i ++) { int cnt = 0; if(col[i].size() == 1) continue; for (auto u : col[i]) { if(d[u] & 1) cnt ++; } num += max(cnt / 2, 1); // 一条链删除两个奇点 => ans >= sum(max(cnt / 2, 1)) // 证明： 构造证明 } cout << num << endl; for (int i = 1; i <= tot; i ++) { if(col[i].size() == 1) continue; int cnt = 0; vector<int> odd; for (auto u : col[i]) { if(d[u] & 1) cnt ++, odd.push_back(u); } if(cnt == 0) { dfs(col[i][0]); cout << ans.size() << ' '; while(!ans.empty()) cout << ans.top() << ' ', ans.pop(); cout << endl; } else { for (int j = 0; j < odd.size(); j += 2) { if(cnt == 2) break; add(odd[j], odd[j + 1], 0); d[odd[j]] ++, d[odd[j + 1]] ++, cnt -= 2; } int st; for (auto u : col[i]) if(d[u] & 1) st = u; dfs(st); while(1) { vector<int> ve; while(!ans.empty() && ans.top() != 0) ve.push_back(ans.top()), ans.pop(); cout << ve.size() << ' '; for (auto v : ve) cout << v << ' '; cout << endl; if(ans.size()) ans.pop(); if(ans.empty()) break; } } } return 0; }
生成树
常用算法：
- kruskal （加边、\(O(m \log_2 m)\)）
- prim (加点、\(O(n^2)\)、适合完全图)
考察方向
生成树上操作
一般和数据结构绑在一起，在求出最小生成树后，根据最小生成树的性质，求解问题。
-
最小生成树边分类
判断每条边是一定出现在最小生成树上还是可能还是不可能
首先先将任意一颗最小生成树找出来，然后讨论每条非树边。
- 如果该边连接的两点在生成树上的边中存在边长与其相等的边，那么该边可以替换这些与其边长相等的边，此时用倍增标记所有与其相等的边，它们也不是唯一的了。
- 否则，这条边一定不存在最小生成树上。
-
次小生成树
首先，次小生成树有一个重要的性质：它与最小生成树的差别只有一条边。证明：
假设将边 \(e1\) 和 \(e2\) 均改为 \(\ge\) 其的边 \(e3，e4\)，可以得到次小生成树。
那么，记除去 \(e1,e2\) 的边权和为 \(res\)，即 \(res + e1 + e2 \le res + e3 + e4\)
即 \(res \le res + e3 - e1 + e4 - e2\)
又因为 \(e3 \ge e1,e4 \ge e2\) 所以后边的书均大于等于 \(0\)，那么只加一个肯定小于等于加两个，所以只改一条边更优。
那么，对于每一条非树边，该边连接的两点在生成树上的边中找出以该边替换后增量最小的，即路径最大值，然后取每条非树边替换后结果的最小值即可。同样的，路径最大值也可以使用倍增维护。
建模
- 跨越雷区
一个点与两个雷区距离的最小值最大化，即这两个雷区距离 \(/ 2\)，所以为了让与雷区距离最大值最小化，不妨连接所有雷区，然后找出最小生成树上最大边，即为路径上最大值距离 \(\times 2\)，答案 \(\2\) 即可。（注意任意雷区可互达，所以是完全图，使用 Prim 算法）
连通性
最关键的：DFS 树
强连通分量
定义不再赘述（虽然上一次总结的时候也没写）。
在处理有环有向图的问题时，如果缩点后每个强连通分量里的信息可以方便处理出来的化，不妨先缩点，然后处理强连通分量内部信息，再在新的 DAG 上，进行拓扑排序、最短路……化繁为简。
双连通分量
该知识点掌握不牢，很多题不会做
性质
边双和点双缩点后均得到一棵树
- 点双
- 每个 \(size > 2\) 的点双中，每一条边都在一个简单环中，特别的，当点数 \(=\) 边数时，该点双中的所有边都仅在一个简单环中。
- 点双中任意两个点都存在两条经过点不相同的路径。
- 点双不具有传递性。
- 非割点仅属于一个点双中。
- 每条边仅属于一个点双中。
- 边双
- \(u, v\) 边双联通即两点间没有必经边。
- 边双联通具有传递性，\(u,v\) 和 \(v, w\) 边双联通，那么 \(u, w\) 边双联通。
- 对于边双内任意一条边 \((u, v)\)，存在经过 \((u, v)\) 的回路。
- 对于边双内任意一点 \(u\)，存在经过 \(u\) 的回路。
解题
如果看到题目中出现：删去某一点，删去某一边，可以往点双或边双的方向想。
az……真写不出来了。
DS
DSU
维护许多树形集合的一种数据结构，复杂度接近常数。
支持操作：
- 合并
- 删除（需要建虚点）
优化：
- 路径压缩（几乎必备）
- 按秩合并
难点：
本体并不算很难，难在运用和建模，一般维护父子结构时可以使用。
单调队列
在 \(O(n)\) 时间内求出每一个长度为 \(k\) 的区间的极值。
同样，本体没什么花样，一般用于优化 DP。
这里重点说优化 DP。
对于形如 \(dp_i = \max_{j = i - k} ^ {i - 1} {dp_j + a_i + b_j}\) 的转移方程，首先尽可能将与变量 \(j\) 不相关的常数移动至循环外，使得循环内的只与 \(j\) 有关，那么此时，循环内的即可用单调队列维护出来。
线段树
本体可以出得很花，运用也可以很广。
本体
一些区间操作，区间查询的裸题，专门考验对线段树的熟练程度。
可能出询问的东西很奇怪，但是可以线段树区间合并来合并出答案的问题。
运用
好像我真的不会用
可以优化 DP，即区间 \(\max,\min,\sum\) 操作时可以使用线段树，一般不需要变动转移方程，直接 updata(dp[i]) 原值即可。
其它的真的不会了。