[Tarjan模板 + topo模板 + dp]洛谷P3387 缩点

传送门：P3387 【模板】缩点 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

顾名思义啊，一个模板题，用tarjan算法缩点之后topo + DAGdp就可以了，写一个模板，防止自己忘记。

代码

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int maxn = 1e4 + 9;

int a[maxn];//点权ai 
vector<int> g[maxn];//存图 
vector<int> G[maxn];//存缩点后的 DAG
int dfn[maxn], low[maxn], col[maxn], tot = 0;//tot为强联通分量编号 
int idx = 0;//idx记录dfn和low的初始值 
int ind[maxn];//表示入度 
//栈，用于表示有哪些子节点 
int stk[maxn], top = 0;
bitset<maxn> ins;//表示是否在栈中 

int max_num(int tmp[],int st,int ed)
{
	int res = 0;
	for(int i = st;i < ed; ++ i)res = max(res, tmp[i]);
	return res;
}

void tarjan(int x)
{
	dfn[x] = low[x] = ++ idx;
	stk[++ top] = x;
	ins[x] = 1;
	
	for(auto& y : g[x])
	{
		//low[y] > dfn[x]判断割边 
		if(!dfn[y]) //如果y没有访问过 
		{
			tarjan(y);
			low[x] = min(low[x], low[y]);
		}
		else if(ins[y]) //如果访问过且在栈中，说明遇到父节点了，要回溯咯 
		{
			low[x] = min(low[x], dfn[y]);
		}
	}
	
	if(dfn[x] == low[x])//遇到了一个小父亲 
	{
		tot ++;//新建一个强联通分量 
		while(stk[top + 1] != x)//直到小父亲也加进去了，说明加完了 
		{
			col[stk[top]] = tot;
			ins[stk[top --]] = 0;
		}
	}
}

int topo(int n)
{
	queue<int> q;
	//由于变量实在太多了，就在堆里面开一下 
	int dp[maxn], val[maxn];
	memset(dp, 0, sizeof dp);
	memset(val, 0, sizeof val);
	for(int i = 1;i <= n; ++ i)val[col[i]] += a[i];
	
	//得到topo的起点 
	for(int i = 1;i <= tot; ++ i)if(!ind[i])q.push(i);
	
	while(!q.empty())
	{
		int x = q.front();q.pop();
		dp[x] = max(dp[x], val[x]);
		for(auto &y : G[x])
		{
			dp[y] = max(dp[y], dp[x] + val[y]);
			ind[y] --;
			if(!ind[y])q.push(y);
		}
	}
	return max_num(dp, 1, tot + 1);
}

signed main()
{
	ios::sync_with_stdio(0);
	
	int n, m;cin >> n >> m;
	for(int i = 1;i <= n; cin >> a[i ++]); // oh这糟糕的码风 
	
	vector<pair<int, int> > v;//存下点，便于加到新图中 
	for(int i = 1;i <= m; ++ i)
	{
		int x, y;cin >> x >> y;
		g[x].pb(y);
		v.pb({x, y});
	}
	
	for(int i = 1;i <= n; ++ i)if(!dfn[i])tarjan(i);
	//构造出了一个有向无环图
	for(auto &i : v)
	{
		int x = col[i.first], y = col[i.second];
		if(x == y)continue;//自环就不连接 
		//如果这条边不存在就加进去 
		if(find(G[x].begin(), G[x].end(), y) == G[x].end())
		{
			G[x].pb(y);
			ind[y] ++;
		}
	}
	
	cout << topo(n) << '\n';
	return 0;
}