题目内容
洛谷链接
有\(n\)位骑士，每个人的战力可能不同，并且每一个人都有且仅有一个憎恨的人，互相憎恨的人不能在同一队中。
求组合为一个骑士队的最大战斗力。
PS：可以去看看题目背景学学历史（雾）
输入格式
第一行包含一个正整数\(n\)，描述骑士团的人数。
接下来\(n\)行，每行两个正整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。
数据范围
\(n ≤ 1 000 000\)，每名骑士的战斗力都是不大于$ 1 000 000$的正整数。
输出格式
输出最大战斗力。
样例输入
样例输出
思路
参考没有上司的舞会
不过还是稍有不同，因为没有上司的舞会是个树，而此题是个有向图，可能存在环之类的。
可以把环断开，两个端点分别深搜。
数组为\(dp[1000000][2]\)，第二维若为1表示选\(i\)点，0则表示不选。用\(j\)表示\(i\)的憎恨者。
转移方程：
\(
\begin{cases}
f[i][1]+=f[j][0],\\
f[i][0]+=max(f[j][0],f[j][1]).\\
\end{cases}
\)
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
const int INF=0x3f3f3f3f;
int n;
ll ans;//可能超int
ll hater[maxn],fight[maxn],dp[maxn][2];
bool vis[maxn];
struct Node{
int x,y;
}c[maxn];
int cnt,head[maxn];
void add(int x,int y){
c[++cnt].x=head[x];
c[cnt].y=y;
head[x]=cnt;
}
void dfs(int x,int g){
vis[x]=1;
dp[x][1]=fight[x];
dp[x][0]=0;
for(int i=head[x];i;i=c[i].x)
if(c[i].y!=g){
dfs(c[i].y,g);
dp[x][1]+=dp[c[i].y][0];
dp[x][0]+=max(dp[c[i].y][0],dp[c[i].y][1]);
}
else dp[c[i].y][1]=-INF;
}
void find(int x){
while(!vis[x]){
vis[x]=1;
x=hater[x];
}
dfs(x,x);
ll temp=max(dp[x][1],dp[x][0]);
x=hater[x];
dfs(x,x);
ans+=max(temp,max(dp[x][1],dp[x][0]));
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x;
scanf("%lld%d",&fight[i],&x);
add(x,i);
hater[i]=x;
}
for(int i=1;i<=n;i++)
if(!vis[i])find(i);
printf("%lld",ans);
return 0;
}