[bzoj 1040] [ZJOI2008]骑士

每个骑士有战斗力和另一个自己厌恶的骑士. 选出一个骑士集合, 使得不存在一个骑士和他厌恶的人同在集合中, 且战斗力之和最大. 求最大战斗力. (骑士数目n≤10^6, 战斗力是不大于10^6的正整数) 所有的边实际上是无向边. 这个定义似曾相识 - 最大权独立集! 它是 NP-hard Problem, 因此本题必有特殊之处. 发现点数和边数相 - 环套树? 把环找出来, 每个子树DP一下, 再对环DP一下. 首尾相互制约, 怎么处理呢? 把环从任意位置断开, 强制第一个点选或不选, 各跑一次DP.

然后WA......这么短的代码都写错? TAT 还是哪一步的分析出了问题?

对拍一下. 还没点开输入文件, 就想到, 为什么认定这是一个环套树呢? 两个分离的三元环, 也有6个点和6条边. 输入是一个环套树森林.

看了看别人的做法, 比我的简单多了......环套树的环从任意位置断开, 就形成了一棵树. 设断开的边是(u,v), 分别以u,v为根, 并强制根不选, 各跑一遍DP即可.

最后, 说一说怎么找环. 我们可能会混淆二元环和邻接表处理无向图时正反各加入一次的边, 但是这样做可以避免这个问题: 记录每个点的发现时间dfn[u], 和它在DFS树上的父亲fa[u]. 如果u,v有边, v还没访问过, 则访问v; 否则, 如果dfn[v]>dfn[u], 说明(v,u)是一条返祖边, 顺着fa即可找到整个环. 注意, fa[u]只是u在这棵DFS树上的父亲, 后面对每棵子树跑DP时就不能用了.

typedef long long ll;

const int N = 1e6;
const ll inf = 1e13;

bool ban[N];
int dfs_clock, m, dfn[N], fa[N], c[N], cir[N];
ll f[2][N], g[2][N];
vector<int> adj[N];

void dfs(int u)
{
	dfn[u] = ++dfs_clock;
	rep (i, 0, adj[u].size()) {
		int v = adj[u][i];
		if (!dfn[v]) {
			fa[v] = u;
			dfs(v);
		} else if (dfn[v] > dfn[u]) {
			do {
				ban[cir[m++] = v] = true;
				v = fa[v];
			} while (v != u);
			ban[cir[m++] = v] = true;
		}
	}
}

void dp_on_tree(int u, int p)
{
	f[1][u] = c[u];
	rep (i, 0, adj[u].size()) {
		int v = adj[u][i];
		if (v == p || ban[v]) continue;
		dp_on_tree(v, u);
		f[1][u] += f[0][v];
		f[0][u] += max(f[0][v], f[1][v]);
	}
}

void dp_on_circle()
{
	rep (i, 1, m) {
		int v = cir[i];
		g[0][i] = f[0][v] + max(g[0][i-1], g[1][i-1]);
		g[1][i] = f[1][v] + g[0][i-1];
	}
}

int main()
{
	int n;
	scanf("%d", &n);
	rep (i, 0, n) {
		int j;
		scanf("%d%d", c+i, &j);
		--j;
		adj[i].push_back(j);
		adj[j].push_back(i);
	}

	ll sum = 0;

	rep (v, 0, n) {
		if (dfn[v]) continue;

		m = 0;
		
		dfs(v);

		rep (i, 0, m)
			dp_on_tree(cir[i], -1);
	
		g[0][0] = f[0][cir[0]];
		g[1][0] = -inf;
		dp_on_circle();
		ll ans = max(g[0][m-1], g[1][m-1]);

		g[0][0] = -inf;
		g[1][0] = f[1][cir[0]];
		dp_on_circle();
		ans = max(ans, g[0][m-1]);

		sum += ans;
	}
	
	printf("%lld\n", sum);
	return 0;
}