代码源 - 基环树

xqy2003 / 2023-08-03 / 原文

ZJOI2008 骑士

自己写的时候建的是 \(dls\) 的反图 , 想的是基环树不是要保证每个点的出度为 \(1\) , 就选择每个点向仇恨点连接一条有向边.
这种情况下如果记录每一个点出度指向哪 , 那么在找环的时候不一定能找到 , 因为图上带环的话要根据入度点找环 (画图理解)
如果记录入度指向哪 , 这是这样建图你不能保证每一个点都有入度
所以按 \(dls\) 的方式建边 , 保证每一个点均有入读点(父亲) ，且满足基环树性质 (反过来入度为 1)

#include <bits/stdc++.h>
using ll = long long;

const ll INF = 1E18;

int main() 
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	
	int n;
	std::cin >> n;
	
	std::vector<std::vector<int>> g(n);
	std::vector<int> val(n) , p(n);
	
	for (int i = 0 ; i < n ; ++i) {
		std::cin >> val[i] >> p[i];
		p[i]--;
		g[p[i]].push_back(i);
	} 
	
	ll ans = 0;
	std::vector<int> vis(n , 0) , oncyc(n , 0);
	std::vector<std::array<ll,2>> dp1(n , {0 , 0}) , dp2(n);
	
	for (int i = 0 ; i < n ; ++i) {
		
		if (vis[i]) continue;
		//利用基环树出度是 1 的性质 
		int u = i;
		while (!vis[u]) {
			vis[u] = 1 ; u = p[u];
		}
		
		int v = u;
		std::vector<int> cyc;
		while (true) {
			oncyc[v] = 1;
			cyc.push_back(v);
			v = p[v];
			if (u == v) break;
		}
		
		std::function<void(int)> dfs = [&] (int u) {
			dp1[u][1] = val[u] , vis[u] = true;
			for (auto v : g[u]) {
				if (oncyc[v]) continue;
				dfs(v);
				dp1[u][0] += std::max(dp1[v][0] , dp1[v][1]);
				dp1[u][1] += dp1[v][0];
			}
		};
		
		//树形 dp 
		int m = cyc.size();
		for (auto v : cyc) 
			dfs(v);
		
		
		//环形 dp , 拆环为链 , 枚举环上第一个点的状态 
		ll res = 0;
		for (int t = 0 ; t < 2 ; ++t) {
			
			for (int s = 0 ; s < 2 ; ++s) {
				if (s != t) dp2[0][s] = -INF;	
				else dp2[0][s] = dp1[cyc[0]][s];
			}
			
			for (int i = 1 ; i < m ; ++i) {
				int u = cyc[i];
				dp2[i][0] =  dp1[u][0] + std::max(dp2[i - 1][0] , dp2[i - 1][1]);
				dp2[i][1] =  dp1[u][1] + dp2[i - 1][0];
			}
			
			if (t == 0) res = std::max({res , dp2[m - 1][0] , dp2[m - 1][1]});
			else res = std::max(res , dp2[m - 1][0]);
		}
		
		ans += res;
		
	}
	
	std::cout << ans << '\n';
	 
	return 0;	
}