【题目来源】
https://www.luogu.com.cn/problem/P2607
https://www.acwing.com/problem/content/1082/
【题目描述】
Z 国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。
最近发生了一件可怕的事情，邪恶的 Y 国发动了一场针对 Z 国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的 Z 国又怎能抵挡的住 Y 国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。
骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。
战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。
为了描述战斗力，我们将骑士按照 1 至 n 编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。
【输入格式】
第一行包含一个整数 n，描述骑士团的人数。
接下来 n 行，每行两个整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。
【输出格式】
应输出一行，包含一个整数，表示你所选出的骑士军团的战斗力。
【输入样例】
3
10 2
20 3
30 1
【输出样例】
30
【数据范围】
对于 30% 的测试数据，满足 n≤10；
对于 60%的测试数据，满足 n≤100；
对于 80%的测试数据，满足 n≤10^4。
对于 100%的测试数据，满足 1≤n≤10^6，每名骑士的战斗力都是不大于 10^6 的正整数。
【算法分析】
· 每个骑士 i 向他讨厌的骑士连一条无向边。
· 共 n 个点、n 条边，且不保证连通 ⇒基环森林。
· 约束“讨厌的两人不能同时选”，使得总战斗力最大 ⇒最大权独立集。
· 挂树部分照常用 f[u][0/1]，“破环”用断边法。其中：
f[u][0]：不选骑士 u 时，以 u 为根的子树最大战斗力；
f[u][1]：选中骑士 u 时，以 u 为根的子树最大战斗力。
【算法代码】
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; typedef long long LL; const int N=1e6+5; vector<PII> roots; vector<int> g[N]; int pre[N],val[N]; LL f[N][2]; int n; int find(int x) { if(x!=pre[x]) pre[x]=find(pre[x]); return pre[x]; } LL dfs(int u,int fa) { f[u][1]=val[u]; f[u][0]=0; for(int j:g[u]) { if(j==fa) continue; dfs(j,u); f[u][1]+=f[j][0]; f[u][0]+=max(f[j][0],f[j][1]); } return f[u][0]; } int main() { scanf("%d",&n); for(int i=1; i<=n; i++) pre[i]=i; for(int i=1; i<=n; i++) { int x; scanf("%d%d", &val[i],&x); int a=find(i); int b=find(x); if(a!=b) { pre[a]=b; g[i].push_back(x); g[x].push_back(i); } else roots.push_back({x,i}); } LL sum=0; for(PII t:roots) { int x=t.first, y=t.second; LL ans=dfs(x,-1); ans=max(ans,dfs(y,-1)); sum+=ans; } printf("%lld",sum); return 0; } /* in: 3 10 2 20 3 30 1 out: 30 */
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/140691777
