题解 P2607 【[ZJOI2008]骑士】

题目链接

Solution [ZJOI2008]骑士

题目大意::给定基环树森林,求带权最大点独立集

基环树,树形(dp)

---

分析:假如是一棵树的话我们朴素树形(dp)就可以搞定,板子题:没有上司的舞会

然后图是基环树森林,显然我们枚举每个联通块分别计算即可

那么怎么在基环树上做(dp),NOIP 2018旅行的思路,断环上一条边变成一棵树

但是我们没有必要枚举断所有的边,既然断边之后失去了这两个点不能同时选的信息,那我们可以人为分类讨论补上

我们任意断一条边后钦定一个点不能选,那么另一个点就可以随意选了,然后两个端点情况取最大值

存图的小(trick:)

如果从仇人向自己连边的话,那么每个点的入度为(1),原图就为外向树,可以省去很多判断

双倍经验:城市规划,这不过这题是无向边要加拓扑排序,基本操作

#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 100;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            
inline int read(){
	int x = 0;char c = getchar();
	while(!isdigit(c))c = getchar();
	while(isdigit(c))x = x * 10 + c - '0',c = getchar();
	return x;
}
vector<int> G[maxn];
int faz[maxn],vis[maxn],val[maxn],root,n;
ll f[maxn][2],ans;
inline void addedge(int from,int to){
	G[from].push_back(to);
	faz[to] = from;
}
void dfs(int u){
	f[u][0] = 0,f[u][1] = val[u];
	vis[u] = 1;
	for(int v : G[u]){
		if(v == root)continue;
		dfs(v);
		f[u][1] += f[v][0];
		f[u][0] += max(f[v][0],f[v][1]);
	}
}
inline ll solve(int now){
	ll res = 0;
	do{
		vis[now] = 1;
		now = faz[now];
	}while(!vis[now]);
	root = now;
	dfs(root);
	res = max(res,f[root][0]);
	root = faz[root];
	dfs(root);
	res = max(res,f[root][0]);
	return res;
}
int main(){
	n = read();
	for(int i = 1;i <= n;i++)
		val[i] = read(),addedge(read(),i);
	for(int i = 1;i <= n;i++)
		if(!vis[i])ans += solve(i);
	printf("%lld
",ans);
	return 0;
}