网瘾犯了。
题意：在 DAG 上删除一点，使得剩下点的最长路最短。
解答：用 \(f_v\) 和 \(h_v\) 表示终点为 \(v\)、起点为 \(v\) 的单源最长路。按照拓扑序（这样才是 DAG，有 dp 性质）枚举 \(u\)，每次先删除所有以 \(u\) 为起点的最长路，再更新答案，随后加入所有以 \(u\) 为起点的最长路。
复杂度：\(\mathcal O(n \log n)\)。
展开代码
#include <bits/stdc++.h>
using ll = long long;
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
std::cin >> n >> m;
std::vector g1(n + 1, std::vector(0, 0)), g2 { g1 };
std::vector deg1(n + 1, 0), deg2{ deg1 };
while (m --) {
int u, v;
std::cin >> u >> v;
g1[u].push_back(v), ++deg1[v];
g2[v].push_back(u), ++deg2[u];
}
std::vector f(n + 1, 0), h { f };
std::vector tsort{ 0 };
auto kahn = [n, &tsort](const auto &g, auto °, auto &f) -> void {
static bool flag = true;
std::queue<int> q;
for (int i = 1; i <= n; i++) {
if (!deg[i]) {
q.push(i);
if (flag) tsort.push_back(i);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u]) {
f[v] = std::max(f[v], f[u] + 1);
if (!--deg[v]) {
q.push(v);
if (flag) tsort.push_back(v);
}
}
}
flag = false;
};
kahn(g1, deg1, f);
kahn(g2, deg2, h);
std::multiset<int> S;
for (int i = 1; i <= n; i++) {
S.insert(h[i]);
}
int id = 0, ans = *--S.end();
for (int i = 1; i <= n; i++) {
int u = tsort[i];
S.erase(S.find(h[u]));
for (int v : g2[u]) {
S.erase(S.find(f[v] + h[u] + 1));
}
if (int res = *--S.end(); ans > res) {
ans = res;
id = u;
}
S.insert(f[u]);
for (int v : g1[u]) {
S.insert(f[u] + h[v] + 1);
}
}
std::cout << id << ' ' << ans << '\n';
return 0;
}