Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
Z 国的骑士团是一个很有势力的组织，帮会中聚集了来自各地的精英。
他们劫富济贫，惩恶扬善，受到了社会各界的赞扬。
可是，最近发生了一件很可怕的事情：邪恶的 Y 国发起了一场针对 Z 国的侵略战争。
战火绵延五百里，在和平环境中安逸了数百年的 Z 国又怎能抵挡得住 Y 国的军队。
于是人们把所有希望都寄托在了骑士团身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。
骑士团是肯定具备打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。
每个骑士有且仅有一个他自己最厌恶的骑士（当然不是他自己），他是绝对不会与最厌恶的人一同出征的。
战火绵延，人们生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！
国王交给你了一个艰巨的任务：从所有骑士中选出一个骑士军团，使得军团内没有矛盾的两人，即不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况，并且使这支骑士军团最富有战斗力。
为描述战斗力，我们将骑士按照 1 至 N 编号，给每位骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力之和。
输入格式
输入第一行包含一个正整数 N，描述骑士团的人数；
接下来 N 行每行两个正整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。
输出格式
输出包含一行，一个整数，表示你所选出的骑士军团的战斗力。
数据范围
N≤106,
每名骑士的战斗力都是不大于 106 的正整数。
输入样例：
3
10 2
20 3
30 1
输出样例：
30
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
const int M = 2 * N;
const int INF = 0x003f3f3f3f3f3f3f;
typedef long long ll;
struct Edge{
int v,next;
}edge[M];
int val[N];
int head[N],cnt;
void add(int u,int v){
edge[cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt ++;
}
ll f[N][2];
int ins[N],st[N],rm[M];
ll ans = 0;
void dfs(int u,int f,int from);
void dfs_c(int u,int from){
st[u] = ins[u] = true;
for(int i = head[u];~i;i = edge[i].next){
if(i == (from ^ 1))continue;
int v = edge[i].v;
if(!st[v])dfs_c(v,i);
else if(ins[v]){
ans = 0;
rm[i] = rm[i ^ 1] = true;
memset(f,0,sizeof f);
dfs(v,-1,-1); // 不选v u可以选可以不选
ans = max(ans,f[v][0]);
memset(f,0,sizeof f);
dfs(v,u,-1); //选v u一定不选
ans = max(ans,f[v][1]);
rm[i] = rm[i ^ 1] = false;
}
}
ins[u] = false;
}
void dfs(int u,int ff,int from){
f[u][0] = 0,f[u][1] = val[u];
for(int i = head[u];~i;i = edge[i].next){
if(rm[i] || i == (from ^ 1))continue;
int v = edge[i].v;
dfs(v,ff,i);
f[u][0] += max(f[v][1],f[v][0]);
f[u][1] += f[v][0];
}
if(ff == u)f[u][1] = -INF;
}
ll res = 0;
int main(){
memset(head,-1,sizeof head);
cnt = 0;
int n,x;
cin>>n;
for(int i = 1;i <= n;i ++){
scanf("%d %d",&val[i],&x);
add(i,x),add(x,i);
}
for(int i = 1;i <= n;i ++)
{
if(!st[i]){
dfs_c(i,-1);
res += ans;
}
}
cout<<res<<endl;
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/168538.html原文链接：https://javaforall.net
