NC50515. 骑士
描述
输入描述
输入第一行包含一个正整数N，描述骑士团的人数；
接下来N行每行两个正整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。
输出描述
输出包含一行，一个整数，表示你所选出的骑士军团的战斗力。
示例1
输入:
3 10 2 20 3 30 1
输出:
30
C++ 解法, 执行用时: 686ms, 内存消耗: 57096K, 提交时间: 2022-06-16 13:54:55
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1000100;
struct node{
int nt,to;
}a[N];
int h[N],fa[N];
int s[N],n,tot,ans,f[N][2];
bool v[N],vis[N];
void add(int x,int y)
{
a[++tot].nt=h[x];
a[tot].to=y;
h[x]=tot;
fa[y]=x;
}
void dfs(int x)
{
v[x]=1;
f[x][1]=s[x];
for(int i=h[x];i;i=a[i].nt)
{
if(v[a[i].to]==0)
{
dfs(a[i].to);
f[x][0]+=max(f[a[i].to][1],f[a[i].to][0]);
f[x][1]+=f[a[i].to][0];
}
}
}
void dp(int x)
{
int root=0;
for(root=x; vis[root]==0; root=fa[root])
{
vis[root]=1;
}
dfs(root);
x=fa[root];
f[x][1]=f[x][0];
for(x=fa[x];x!=root;x=fa[x])
{
f[x][1]=s[x];
f[x][0]=0;
for(int j=h[x];j;j=a[j].nt)
{
f[x][1]+=f[a[j].to][0];
f[x][0]+=max(f[a[j].to][1],f[a[j].to][0]);
}
}
f[root][1]=s[root];
for(int i=h[x];i;i=a[i].nt)
{
f[root][1]+=f[a[i].to][0];
}
ans+=max(f[root][1],f[root][0]);
}
signed main()
{
cin>>n;
for(int i=1; i<=n; i++)
{
int u;
cin>>s[i]>>u;
add(u,i);
}
for(int i=1;i<=n;i++)
if(v[i]==0)dp(i);
cout<<ans<<endl;
return 0;
}