[ZJOI2008]骑士

P2607

基环树板子题（虽然打了好久好久）

题目大意是给你一n个人的能力值，在每个人都有一个死敌不能同时被选中的情况下，从中挑出一些人，问能力值最大是多少。
首先，为什么会往基环树的方向思考呢？

1. 两两死对头关系可以当作二人之间连一条边
2. 如此一来，就有n条边
3. n个点n条边，显然构成基环树

有了大致方向，再来思考一下具体实现。
首先要明确，基环树的构造是形如这样的：

（就是一个环，每个节点都延伸出一棵子树）
由于我们给死对头连边，问题就转换为了求有间隔地选出最大权值。
那么，我们可以先考虑每一个环上节点延伸的子树。十分显然，在每棵子树上“有间隔地选出最大权值”就是那道经典题目——没有上司的舞会。
好的，现在处理完了每一棵子树，考虑整个环的情况。本来以为到这里就结束了呢，可事情没那么简单。
对于整个环也是一样，我们要“有间隔地选出最大权值”。经试验，贪心是不行的。必须要进行动归。
在环做dp显然是不现实的（后效性），考虑破环为链。假定一个开始点，注意到它的选与不选只会影响到下一个以及上一个点，而且说是会影响第二个点，实际上也没有改变递推式！

所以我们只用分类讨论第一个点选或不选，然后暴力定最后一个点的状态即可。
好的，讲了这么久有的没的，发现漏讲怎么找环了。
这个题的特殊性导致了每个节点的出度只能为1。
所以对于每一个环上节点对应的子树，它的形态必定是这样的：

环内又必定是这样的：

所以不难发现，即使我们现在访问的是随意一个节点，我们最后也会绕到环里边。如果一个点被经过了2次就说明它一定在环上（一次从子树出来，一次绕着环回来）
接着，我们又利用环的形态性质就可以简单地 for (int i = f[st]; i != st; i = f[i]) 访问
代码如下qaq

#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
#define int long long
const int maxn = 1e6+100;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n,w[maxn],f[maxn],st,ans;
bool vis[maxn], circle[maxn];
int dp[maxn][2], cur[5], chose[maxn][2];
vector<int> adj[maxn];
void find(int u) {
//	cout << u << endl;
	if (vis[u]) {
		st = u;
		return;
	}
	vis[u] = true;
	find(f[u]);
}

void dfs(int u, int fa) {
	vis[u] = 1;
	dp[u][0] = 0, dp[u][1] = w[u];
	for (auto v:adj[u]) {
		if (v != fa && !circle[v]) {
//			cout << "shit" << endl;
			dfs(v,u);
			dp[u][0] += max(dp[v][0], dp[v][1]);
			dp[u][1] +=  dp[v][0];
		}
	}
}

void DP() {
	circle[st] = 1;
	for (int i = f[st]; i != st; i = f[i]) vis[i] = 1, circle[i] = 1;
	int u = st, cnt = 0;
	while (true) {
		if (cnt && u == st) break;
		cnt = 1;
		dfs(u,0);
//		printf("dp[%d][0] = %d; dp[%d][1] = %d\n",u,dp[u][0],u,dp[u][1]);
		u = f[u];
	}
}

void choose() {
	int res;
	//choose first one
	chose[st][0] = -INF, chose[st][1] = dp[st][1];
	int lst = st;
	for (int i = f[st]; i != st; i = f[i]) {
		chose[i][0] = max(chose[lst][1],chose[lst][0]) + dp[i][0];
		chose[i][1] = (chose[lst][0] == -INF)?-INF :chose[lst][0]+dp[i][1];
		lst = i;
	}
	res = chose[lst][0];
	//don't choose 1st
	chose[st][1] = -INF, chose[st][0] = dp[st][0];
	lst = st;
	for (int i = f[st]; i != st; i = f[i]) {
		chose[i][0] = max(chose[lst][1],chose[lst][0]) + dp[i][0];
		chose[i][1] = chose[lst][0]+dp[i][1];
		lst = i;
	}
	ans += max(max(chose[lst][1],chose[lst][0]),res);
}

signed main() {
//	freopen("2.in","r",stdin);
	scanf("%lld",&n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld%lld",&w[i],&f[i]);
		//son tree dp
		adj[i].push_back(f[i]), adj[f[i]].push_back(i);
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			find(i);
//			cout << st << endl;
			DP();
			choose();
		}
	}
	printf("%lld\n", ans);
	return 0;
}
/*
10
30 2
20 3
20 1
15 1
25 1
22 5
14 2
26 7
24 3
30 3
*/

原文地址：http://www.cnblogs.com/mostlyhms/p/16897900.html