P2607 [ZJOI2008]骑士
P2607 [ZJOI2008]骑士
认真的写题解，（我都不信）咳咳，学习！！
我们看完这道题应该思路很清晰，清晰到题意都忘了，咳！
再看一遍，咦~“真龙天子的降生，带领正义打败邪恶。”谁？谁喊我来着？
心平气和，我要拯救世界，呼~吸~
咳咳，看完题意，嗯，我的眼中闪着智慧的光芒，
点开旁边的算法标签，--动态规划,…… 嗯， 动规dp…… 嗯， 搜索 ……嗯，算个好题 树形动规…… 嗯，还好都会……（擦汗） 环套树 “环套树”嗯！！？(⊙_⊙)? 啊，谁关灯？（心虚……）我咋没看到这道题？我刚才好像啥都没点，啥都没看见……对……
嗯……（尴尬的气氛）是不是该吃饭了？
我先吃个饭啊……（滚溜）
一天后……，
我昨天是不是看过一道环套树？昨天咋没写？唉？肯定是忘了，嗯嗯，对；
认真解题：
题目大意：n位骑士，每个人的战力可能不一样，并且每一个人都有一个厌恶对象；求组合为一个骑士团，骑士团的最大战力；
这道题，可以抽象为n个点n条边的无向图。如果我们把它想象为一个有向连通图，那问题就变得简单了起来，；着了插入一个关于基环树的概念；虽说在看的dalao应该都会……为什么要用基环树下面自然就知道了
下面我们讲解基环树：
这是一棵普通的基环树： 对于基环树，我们主要分为两种：一种叫做基环内向树，另一种基环外向树；具体的区别；
基环内向树是每个点只有一条出度，如下图：
基环外向树是每个点只有一条入度，如下图：
这是基环树的大概定义；；
那对于这道题，，有啥用？
首先： 我们可以将骑士所仇恨的人和他自己连一条线，单向的（可以将仇恨的人指向自己，也可以自己指向仇恨的人）；两种方法都可以；
那现在我们就可以将这个问题转化为在基环外向树上找权值最大的独立集的问题；
那事情就变得简单了起来，我们现在的主要问题就是：如何找根？？
这个问题，，朴素做法：我们对于每一个点都作为根节点，然后dp，
这是比较好想的算法，那我们可以尝试这样写一下，很慢……很慢……很慢……
对于好一点的方法：
我们设f[i][0],,f[i][1];记f[v][0]为不选当前节点的最大值，f[v][1]为选择当前节点后的最大值，ans取较大者即可。
我们找到环上的一条边，把这条边中的一个点选成根进行dp，这个时候，根节点的f[root][0]一定是准确的，但是f[rt][1]是不准确的，我们必须强制这条边的另一个点不选，然后将这个状态走环一圈，再用来更新f[rt][1]
由于每个点的仇恨的人向自己连一条边，那么入度必然是1，我们可以直连单向边，然后记录指向自己的人作为父亲，每个点顺着父亲走必然可以走到环上
大概应该就是这样
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1000100;
struct pp{
int next,to;
}a[N];
int head[N],fa[N];ll s[N],n,tot,ans,f[N][2];
bool v[N],v1[N];
void add(int x,int y){
a[++tot].next=head[x];
a[tot].to=y;
head[x]=tot;
fa[y]=x;
}
void ss(int x){
v[x]=1;
f[x][1]=s[x];
for(int i=head[x];i;i=a[i].next){
if(v[a[i].to]==0){
ss(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(ll x){
int root;
for(root=x;v1[root]==0;root=fa[root]){ //寻找环，该循环会在有环的情况下--退出；^ ^
v1[root]=1;//标记一下
}//cout<<root<<endl;
ss(root);
x=fa[root];//cout<<x<<endl;
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=head[x];j;j=a[j].next){
f[x][1]+=f[a[j].to][0];
f[x][0]+=max(f[a[j].to][1],f[a[j].to][0]);
}
}//cout<<f[root][1]<<" "<<f[root][0]<<endl;
f[root][1]=s[root];
for(int i=head[root];i;i=a[i].next){
f[root][1]+=f[a[i].to][0];
}//cout<<f[root][1]<<endl;
ans+=max(f[root][1],f[root][0]);
}
int main()
{
scanf("%lld",&n);
ll q;
for(int i=1;i<=n;i++){
scanf("%lld%lld",&s[i],&q);
add(q,i);
//cout<<q<<"-->"<<i<<endl;
}
for(int i=1;i<=n;i++){
if(v[i]==0)dp(i);
}
printf("%lld",ans);
return 0;
}