\(\color{green}(1)\) CF721C Journey
- 给定一张 \(n\) 个点 \(m\) 条边的有向无环图，边有边权。构造一条 \(1 \to n\) 的路径使得其边权和 \(\le k\) 且经过的点数最多。
- \(n, m \le 5 \times 10^3\)，\(k \le 10^9\)。
最简单的想法是设状态 \(f_{i, j}\) 表示 \(1 \to i\) 的边权和 \(\le j\) 的路径的最多点数。那么答案为 \(f_{n, k}\)。
显然状态数会爆炸。参照 AT_dp_e 的思路，我们将状态和值交换，即重新令 \(f_{i, j}\) 表示 \(1 \to i\) 的路径上经过了 \(j\) 个点的最小边权和。剩下的就是平凡的转移了。
\(\color{green} (2)\) CF731C Socks
- 你有 \(n\) 只袜子，共有 \(k\) 种颜色，有 \(m\) 天。每只袜子有它的初始颜色。在第 \(i\) 天，你会穿第 \(l_i\) 只和第 \(r_i\) 只袜子。求最少改变多少袜子的颜色，使得你每天穿的两只袜子颜色相同。
- \(n, k, m \le 2 \times 10^5\)。
将 \(l_i, r_i\) 连边，会形成若干个连通块。显然每个连通块内的袜子颜色应该是相同的。
对于每个连通块独立考虑。我们希望将这个连通块内的颜色统一，且操作次数最少，最直观的想法就是全部染成出现次数最多的颜色。
令连通块大小为 \(s\)，最多的颜色出现了 \(t\) 次，那么答案即 \(\sum (s - t)\)。
\(\color{green}(3)\) CF412D Giving Awards
- 请你构造 \(1 \sim n\) 排列 \(P\)，满足给定的 \(m\) 条形如 \((u, v)\) 的限制，表示不存在 \(P_i = u\) 且 \(P_{i + 1} = v\)。保证不存在两个限制 \(\mathbf{(u, v)}\) 和 \(\mathbf{(v, u)}\)。
- \(n \le 3 \times 10^4\)，\(m \le 10^5\)。
连 \(u \to v\) 的有向边，然后 dfs 整张图。在 \(u\) 的出边全部访问结束后，将 \(u\) 加入答案队列的队尾。
考虑证明这种构造一定是正确的。可以画出一颗 dfs 树，分析三种边的合法性：
- 树边，例如 \(4 \to 5\)。根据我们的做法，\(4\) 一定在 \(5\) 之后访问。这样是合法的。
- 返祖边，例如 \(3 \to 1\)。由于题目保证「不存在两个限制 \((u, v)\) 和 \((v, u)\)」，所以这条返祖边一定不是指向它的父亲，而是跨越至少一个点。这意味着尽管有 \(3 \to 1\) 这条边，但由于 \(1\) 是祖先，所以它已经在前面被访问过，再次访问到 \(3\) 时它们之间已经隔着若干个点了（例如图中的 \(2\)）。所以这样是合法的。
- 横叉边，例如 \(5 \to 3\)。同样的思路，在树上 \(3, 5\) 一定不是直接相连的，而是隔着几个点。这样也是合法的。
$\color{blue}\text{Code}$
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m;
vector<int> g[N];
bool st[N];
void dfs(int u) {
if (st[u]) return;
st[u] = true;
for (int v : g[u]) dfs(v);
cout << u << ' ';
}
int main() {
cin >> n >> m;
while (m -- ) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
}
for (int i = 1; i <= n; ++ i ) dfs(i);
return 0;
}
\(\color{blue} (4)\) CF118E Bertown roads
- 给定一张 \(n\) 个节点 \(m\) 条边的无向联通图。构造一种为每条边都确定一个方向的方案，使得这张图成为一个 scc。或报告无解。
- \(n \le 10^5\)，\(m \le 3 \times 10^5\)。
若原图不是一个 dcc，即存在桥，那么一定无解。这是显然的。
否则，我们建一颗 dfs 树，并将树边的方向定为 父亲 \(\to\) 儿子，将返祖边的方向定为 后代 \(\to\) 祖先。显然不存在横叉边。
考虑证明这样做是可行的：
- 由于树边都是向下指，所以祖宗可以到达它的所有后代，包括但不限于祖先可以到达所有节点。
- 对于叶子节点，由于图中不存在桥，所以它一定存在一条返祖边。而这条边指向的祖宗要么为根，要么也存在一条返祖边。以此类推。所以叶子节点总能到达根。然后到达所有节点。
- 对于一般的节点，它可以通过树边到达叶子，再到达根，再到达所有节点。