题解 P3387 【模板】缩点
Warriors_Cat
2020-04-20 21:55:09
大致浏览了一下，似乎在缩点这一块几乎没有跟我的做法相似的……
于是发了个题解，讲一讲我的教练教给我的做法吧。
---
如果这个图是一个有向无环图（DAG），则可以用动态规划的思想进行求最长路。但，这是一张图，说明其中有环，这就比较麻烦了。
于是，我们要把环缩成一个点，这样就可以跑 DAG 了。于是，我们想要的就是：缩点。
---
首先介绍几个概念：
* 强连通：有向图中两点能互相到达，那么它们强连通。
* 强连通图：任意两点能够互相到达的有向图叫做强连通图。
* 强连通分量：有向图的极大强连通图子图叫做强连通分量。
对于这道题，我们只要把强连通分量缩成一个点就行了，因为这两个点可以互相到达，在这当中选任意一个点，结果也一样。
那，如何求强连通分量呢？
我们进行 dfs，定义每个点有三个状态：没搜索（0），搜索中（正），搜索完（负）。如果在搜索的过程中，搜到了正在搜索的点，说明**它们可以互相到达，属于同一个强连通分量（重点！）**。
把它们合并在一个强连通分量里？想到了并查集！
我们可以用并查集维护它们缩成的点，一开始每个点都是一个强连通图，即 $f[i] = i$。在搜索时，如果遇到没搜索的点，就继续搜；如果遇到搜索完的点，就不需再搜了；如果遇到一个搜索中的点，就用并查集合并。
但，这里要注意，合并时**必须是先搜到的点为祖先节点（重点！）**，如果用后搜到的点作为祖先节点，那么后搜的搜完后，强连通分量就搜完了，答案就不准确。
具体代码如下：
```cpp
void dfs(int u){
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].v;
if(!vis[v]){//如果没搜索
vis[v] = vis[u] + 1;//记录“深度”
dfs(v);//继续搜
}
int fu = anc(u), fv = anc(v);//anc 是并查集函数
if(vis[fv] > 0){//一定要是搜索中的
if(vis[fu] < vis[fv]) f[fv] = fu;
else f[fu] = fv;//注意这里，深度小的为祖先节点
}
}
vis[u] = -1;//标记搜索完
return;
}
```
----
接着，我们再把缩完的点的权值更新一下，更新方法就是把自己的权值加在祖先节点上。
然后，我们重新建图，如果原来一条边上的两个点的祖先节点不属于同一个强连通分量，那么就把这两个祖先节点连一条边，同时记录入度。
最后跑一遍 toposort 就行了，toposort 的话其它题解都有提到，这里就不再赘述了。
---
下面放一下 AC 代码：（较完整注释）
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define N 100010
struct edge{
int u, v, nxt;
}e[N];
queue <int> q;
int head[N], cnt, n, m, x, y, vis[N], f[N], c[N], s[N], r[N], ans = 1, W[N];
inline void add(int u, int v){
e[++cnt].u = u;//注意要把 u 也给加上，后面需要调用
e[cnt].v = v;
e[cnt].nxt = head[u];
head[u] = cnt;
}
int anc(int x){
if(x == f[x]) return x;
return f[x] = anc(f[x]);
}//并查集模板
void dfs(int u){
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].v;
if(!vis[v]){//如果没搜索
vis[v] = vis[u] + 1;//记录“深度”
dfs(v);//继续搜
}
int fu = anc(u), fv = anc(v);//anc 是并查集函数
if(vis[fv] > 0){//一定要是搜索中的
if(vis[fu] < vis[fv]) f[fv] = fu;
else f[fu] = fv;//注意这里，深度小的为父亲
}
}
vis[u] = -1;//标记搜索完
return;
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i) f[i] = i, scanf("%d", W + i);
for(int i = 1; i <= m; ++i){
scanf("%d%d", &x, &y);
add(x, y);
}
for(int i = 1; i <= n; ++i){
if(!vis[i]){//如果这个点还没搜索就要继续搜
vis[i] = 1;
dfs(i);
}
}
for(int i = 1; i <= n; ++i) c[anc(i)] += W[i];//缩点权值处理
memset(head, 0, sizeof(head));
cnt = 0;//这里要清零哦-v-
for(int i = 1; i <= m; ++i){
x = f[e[i].u], y = f[e[i].v];//由于在上面已经全部遍历过 anc 函数了，这里直接调用即可
if(x != y) add(x, y), r[y]++;//不在一个强连通分量就连边
}
for(int i = 1; i <= n; ++i){
if(i == f[i] && !r[i]) q.push(i), s[i] = c[i];
}//s[i] 是 dp 数组
while(!q.empty()){
int u = q.front(); q.pop();
for(int i = head[u]; i; i = e[i].nxt){
int v = e[i].v;
s[v] = max(s[v], s[u] + c[v]);
if(--r[v] == 0) q.push(v);
}
ans = max(ans, s[u]);
}//toposort 模板
printf("%d", ans);
return 0;
}
```