题解 P7516 【[省选联考 2021 A/B 卷] 图函数】
Lice
2021-04-12 20:24:36
这里有一个靠谱复杂度的做法 qwq
### Description & Hint
原题意够形式化了吧 [qwq](https://www.luogu.com.cn/problem/P7516)
### Solution
原来打爆我的不是最短路，而是 Bfs。参考了 @Grice 的 [做法](https://www.cnblogs.com/Grice/p/14645327.html)，不过这位大佬写的过于简洁，好久才悟 /dk，写篇题解理理思路，作为复盘。
首先还是一些常规的转化。我们自然不考虑求出每个 $f(u,G)$ 的值，而尝试直接算出有多少顶点对 $(u,v)$ 会对 $h(G_i)$ 产生贡献，毕竟需要我们细化分别求出的是 $h$ 而不是 $f$。
其次，考虑一个点 $v$ 对 $f(G,u)$ 的何时会产生贡献：存在 $u\to v$、$v\to u$ 两条路径，其上只存在编号 $\ge v$ 的点。可不可能通过一个 $<v$ 的点 $k$ 找到这两条路径呢？考虑 $u\to v\to u$ 这已经形成一个环了，那其上的 $k$ 势必会在之前被删掉，任何这样的 $k$ 都不能被这两条路径利用，一旦可以被利用你会发现它们在之前就莫得了。
现在问题转化为：对于每个图 $G,G_1, G_2, \cdots, G_m$，分别求有多少顶点对 $(u, v)$（$u\ge v$），存在两条不经过编号 $<v$ 的顶点的路径 $u\to v$、$v\to u$（下面简称这样的路径为“合法路径”）。
我们再换个角度，从顶点对的方向突破。很显然一个点对会对一个答案的前缀产生贡献。设合法路径 $u\to v$、$v\to u$ 上经过的边的编号最小值最大化为 $x$，其中最小值是产生贡献前缀的大小，而最大化是因为我们希望它产生最大的贡献。最后可以求出答案的差分数组，一波后缀和即可出解。
这时已经有一个最短路的模型了，可以用经典的 Floyd 或 Dijkstra 解决，复杂度为 $O(n^3+m)$ 或 $O(nm\log n)$，但都很卡（全世界就我跑不动 $1000$ 的 Floyd）。
接下来是一个高明的 $O(n(n+m))$ 的做法（为什么我都想不到/kk）。对每个点 $v$，考虑其对 $f(u,G)$ 产生的贡献。那么我们只要保留 $[v, n]$ 的点，对 $O(m)$ 张图分别求出其能到的点数，一次 Bfs $O(m)$。这样复杂度很高，是 $O(nm^2)$ 的。
于是考虑一个优化：我们不对 $O(m)$ 张图都求一遍，而是每次倒着加边。对于一条新边 $(a,b)$，如果 $a$ 被遍历过而 $b$ 没有，那么现在这条边将派上用场，之前到达过 $a$，现在直接从 $b$ 开始 Bfs 即可。如果 $a,b$ 都没遍历过，那么它可能会在以后起作用，先加到图中。其他情况，那这边就一点用没有。注意正反图都要这么操作。而在 Bfs 时，我们会把用过的边删去，不难发现这些边在之后不会被用到，所以不影响正确性。由于每条边只会用一次，过河拆桥，于是总复杂度为 $O(n(n+m))$ 的（由于是根据我自己的理解写的，可能没点到重点，有疑问敬请指出）。
### Code
```cpp
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <vector>
#include <queue>
const int N = 1e3 + 5;
const int M = 2e5 + 5;
int n, m;
int U[M], V[M];
int ans[M]; // h(G_i)
int vis[2][N];
std::vector<int> adj[2][N];
void Bfs(int g, int s, int t) {
std::queue<int> que;
vis[g][s] = t, que.push(s);
while (!que.empty()) {
int x = que.front(); que.pop();
for (auto y : adj[g][x]) if (!vis[g][y])
vis[g][y] = t, que.push(y);
adj[g][x].clear();
}
}
signed main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
scanf("%d%d", U + i, V + i);
for (int i = 1; i <= n; i++) { // i -> f(j, G), j >= i
for (int g = 0; g < 2; g++)
for (int j = 1; j <= n; j++)
adj[g][j].clear(), vis[g][j] = 0;
vis[0][i] = vis[1][i] = m + 1;
for (int j = m; j >= 1; j--) {
if (std::min(U[j], V[j]) < i) continue;
for (int g = 0; g < 2; g++, std::swap(U[j], V[j]))
if (vis[g][U[j]] && !vis[g][V[j]])
Bfs(g, V[j], j);
else if (!vis[g][U[j]] && !vis[g][V[j]])
adj[g][U[j]].push_back(V[j]);
}
for (int j = i; j <= n; j++) if (vis[0][j] && vis[1][j])
ans[std::min(vis[0][j], vis[1][j]) - 1]++;
}
for (int i = m; i >= 0; i--)
ans[i] += ans[i + 1];
for (int i = 0; i <= m; i++)
printf("%d ", ans[i]);
return 0;
}
```