【算法小结】tarjan缩点+拓扑求有向有环图的路径点权之和最大值

洛谷 -----【模板】缩点

先利用tarjan算法将环上的点权全部聚集在一个点上，即化环为点；再通过拓扑排序从头开始走，利用动态规划dp[v]=max(dp[v]，dp[u]+point[v])求得从头开始走到的某点的最大点权和。即可求出答案。

环即最大联通分量

#include
using namespace std;
const int N = 10005;
int n, m, sum, tim, top, s;
int p[N], head[N], sd[N], dfn[N], low[N];
//某点汇聚环内点后的权值，链式前向星的头，类并查集记录环的根，时间戳，最小后代戳
int stac[N], vis[N];
//模拟栈，记录是否在栈中
int h[N], in[N], dist[N];
//缩点后的图的链式前向星的头，某点的入度，dist[i]表示从起点到点i的最大点权之和
struct edge {
	int to, next, from;
}edge[N*10],ed[N*10]; //点缩前后的链式前向星的存边数组
void add(int x, int y) {
	edge[++sum].next = head[x];
	edge[sum].from = x;
	edge[sum].to = y;
	head[x] = sum;
}
void tarjan(int x) {
	dfn[x] = low[x] = ++tim;
	stac[++top] = x; vis[x] = 1;
	for (int i = head[x]; i; i = edge[i].next) {
		int v = edge[i].to;
		if (!dfn[v]) {
			tarjan(v);
			low[x] = min(low[x], low[v]);
		}
		else if (vis[v]) {
			low[x] = min(low[x], low[v]);
		}
	}
	if (dfn[x] == low[x]) {
		int y;
		while (y = stac[top--]) {
			sd[y] = x; //将点y的sd设置为其所在环的根，类似并查集
			vis[y] = 0; 
			if (x == y) break; 
			p[x] += p[y]; //该环的根的进行点权汇聚
		}
	}
}
int topo() {
	queue q;
	int tot = 0;
	for (int i = 1; i <= n; i++) {
		if (sd[i] == i && !in[i]) { //sd[i]==i时表明该点是化环为点后的缩点，p[i]已经汇聚了该环的所有点权之和
			q.push(i);
			dist[i] = p[i];
		}
	}
	while (!q.empty()) {
		int k = q.front(); q.pop();
		for (int i = h[k]; i; i = ed[i].next) {
			int v = ed[i].to;
			dist[v] = max(dist[v], dist[k] + p[v]); //dp
			in[v]--;
			if (in[v] == 0) q.push(v);
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans = max(ans, dist[i]);
	}
	return ans;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> p[i];
	for (int i = 1; i <= m; i++) {
		int u, v; cin >> u >> v;
		add(u, v);
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i]) tarjan(i);
	}
	for (int i = 1; i <= m; i++) {
		int x = sd[edge[i].from], y = sd[edge[i].to];
		if (x != y) { //当且仅当边的两端点不是同一个环上的时候，才可以将其各自的环根加入点缩后的图中
			ed[++s].next = h[x];
			ed[s].from = x;
			ed[s].to = y;
			h[x] = s;
			in[y]++;
		}
	}
	cout << topo() << endl;
	return 0;
}