本文共 2801 字，大约阅读时间需要 9 分钟。

有向图缩点 / 【模板】缩点

题目链接： /

题目大意

有一个有向图，你要从一个点走到一个点，点有权值，途中进过点权值和为分数。

点重复经过只算一次，要你输出最大分数。起点终点自己定。

思路

这道题就是模板题。

首先，我们来讲讲为什么要缩点。

缩点，既是把一个强连通子图缩成一个图，然后维护性质。那它的用处就是可以让一个有向有环图变成一个有向无环图。

那因为这道题点多次经过只算一次，那我们可以把缩后的点的权值弄成被缩成它的所有点的权值之和。

因为如果进过了缩后的点，那就相当于把被缩成它的所有点都经过了一次或以上，那权值就是这个了。

那把图通过这样改成 DAG 之后，我们就可以按着拓扑排序的方式依次 dp。最后枚举终点，就可以得出答案了。

那具体怎么缩点呢？

我这里使用的是 Tarjan 算法。 它主要的算法思想就是把每个连通块都看成是一个 DFS 搜索树。

对于一个连通块，我们把里面的边分成四种：

1. 在 DFS 搜索树上的边，叫做树枝边。
2. 在 DFS 搜索树上的从根节点出发的一条链上，而且是指向儿子的，叫做前向边。
3. 在 DFS 搜索树上的从根节点出发的一条链上，叫做后向边。
4. 这两个点不是在从根节点出发的一条链上，那就叫做横叉边。

那我们考虑怎么才会形成环。

那你肯定是要有后向边或者横叉边才行啊。 你是后向边的话，就一定会有它组成的环，但是如果是横叉边呢？ 你会发现它有可能有包含在环中，也有可能不包含。 然后你会发现它连向的点没有已经强连通的时候，它其实就不能跟它们形成环之类的，否则就是可以的。

那我们可以这样，弄 $df{n}_i$ 表示 dfs 序，然后再弄一个 $lo{w}_i$。

当出现后向边和连向没有在环中的点的横叉边的时候，我们就记录一下连向的点的编号。 但是因为可能有很多个环，那我们可以把没有连通而且搜到过的点按 dfs 序放进一个栈中，然后 $lo{w}_i$ 一开始跟 $df{n}_i$ 相同，然后碰到环就取连向的点的 $lo{w}_i$ 值，然后取最小值。 然后怎么看它会在一个新的中呢？ 你可以看出 $lo{w}_i$ 是指向它的环中的一个点的，那如果还是跟 $df{n}_i$ 一样，那就是自己独立成点或者是一个连通分量的标志点。

那你就可以确定新的连通分量是否出现，然后你会想到栈中在这个点前面的点都是这个连通分量的点，那你就一直出栈，就可以把每个点都找到。这个时候就可以计算缩后点的各项值了。

代码

#include
   
    #include
    
     using namespace std;struct node {   	int to, nxt;}e[100001], e_[100001];int n, m, a[10001], le[10001], KK, st[10001], tot, top;int x, y, dfn[10001], low[10001], num, in[10001], ans;int sum[10001], le_[10001], KK_, ru[10001], dis[10001];queue 
     
       q;void add(int x, int y) {   	e[++KK] = (node){   y, le[x]}; le[x] = KK;}void add_(int x, int y) {   	e_[++KK_] = (node){   y, le_[x]}; le_[x] = KK_;}void tarjan(int now) {   //Tarjan缩点	dfn[now] = low[now] = ++num;	st[++top] = now;		for (int i = le[now]; i; i = e[i].nxt)		if (!dfn[e[i].to]) {   			tarjan(e[i].to);			low[now] = min(low[now], low[e[i].to]);		}		else if (!in[e[i].to]) low[now] = min(low[now], low[e[i].to]);		if (dfn[now] == low[now]) {   		in[now] = ++tot;		sum[tot] = a[now];//算出缩后的点的总权值		while (st[top] != now) {   			in[st[top]] = tot;			sum[tot] += a[st[top]];//算出缩后的点的总权值			top--;		}		top--;	}}int main() {   	scanf("%d %d", &n, &m);	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);	for (int i = 1; i <= m; i++) {   		scanf("%d %d", &x, &y);		add(x, y);	}		for (int i = 1; i <= n; i++)		if (!dfn[i]) tarjan(i);		for (int i = 1; i <= n; i++)		for (int j = le[i]; j; j = e[j].nxt)			if (in[i] != in[e[j].to]) {   //建缩点后的图				add_(in[i], in[e[j].to]);				ru[in[e[j].to]]++;			}		for (int i = 1; i <= tot; i++)//想跑最长路一样跑DAG		if (!ru[i]) {   			q.push(i);			dis[i] = sum[i];		}	while (!q.empty()) {   		int now = q.front();		q.pop();				for (int i = le_[now]; i; i = e_[i].nxt) {   			dis[e_[i].to] = max(dis[e_[i].to], dis[now] + sum[e_[i].to]);			ru[e_[i].to]--;			if (!ru[e_[i].to]) q.push(e_[i].to);		}	}		for (int i = 1; i <= tot; i++)		ans = max(ans, dis[i]);//看终点在哪里最优		printf("%d", ans);		return 0;}