基环树DP
什么叫基环树DP啊？
谢罪谢罪
在图论中，树被视作为一种特殊的图G=(V, E)，其中|V| = |E|+1。其存在如下特性：
1.树G上任意两点必定能够通过途经若干边后到达2.任意两点间的路径必然唯一，即不存在环3.将树G上任意一条边删去，该图即成为非连通图4.在G中任意不相连两点间插入一条边，该新图G’ =(V, E’)正好含有一个环基环树的概念即是从上述特性4所引申出的特殊的树。虽然其不符合树|V| = |E| + 1的特征，但由于其特殊性——删除环上任意一条边即可成为树，故仍将其视作”树”来解决问题。
因此可以枚举删边进行树上DP，但要注意保持环的性质，即注意被删边两点之间的关系。
题目描述
战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。
为了描述战斗力，我们将骑士按照1至N编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。
输入输出格式
输入格式：
第一行包含一个正整数N，描述骑士团的人数。
接下来N行，每行两个正整数，按顺序描述每一名骑士的战斗力和他最痛恨的骑士。
输出格式：
包含一个整数，表示你所选出的骑士军团的战斗力。
solution
将每个骑士所憎恨的人和他连一条单向边，再将骑士的父节点设为他憎恨的人，这样就形成了一个图，容易得出这个图中一定存在环，且我们将一个个环断开就会生成一个树，然后就是简单的树上DP（没有上司的舞会），有几点要注意
1.注意判好所有环，这个图有可能不是联通的，所以每个强连通分量都是独立的
2.注意断环时要注意两个端点的关系，不能两个同时选，因此可以分别强制一个不选，然后对两个点都进行DP取max
3.DP过程注意顺便把vis赋值
4.对于每一个环考虑到树的性质，只对断边的两个端点DP即可。
code
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
#define maxn 2000010
#define re register
using namespace std;
int n,cnt,root,y;
ll ans,DP[maxn][2];
int head[maxn],vis[maxn],val[maxn],fa[maxn];
struct Edge{
int v,nxt;
}e[maxn];
inline void add(
int u,
int v)
{
e[++cnt].v=
v;
e[cnt].nxt=
head[u];
head[u]=
cnt;
}
inline int read()
{
int x=
0,f=
1;
char ch=
getchar();
while(ch<
'0'||ch>
'9'){
if(ch==
'-')f=-
1;ch=
getchar();}
while(ch>=
'0'&&ch<=
'9'){x=x*
10+ch-
'0';ch=
getchar();}
return x*
f;
}
void dp(
int now)
{
vis[now]=
1;
DP[now][0]=
0,DP[now][
1]=
val[now];
for(
int i=head[now];i;i=
e[i].nxt)
{
int ev=
e[i].v;
if(ev!=
root)
{
dp(ev);
DP[now][0]+=max(DP[ev][
1],DP[ev][
0]);
DP[now][1]+=DP[ev][
0];
}
else
{
DP[ev][1]=-
maxn;//关键，实际上是控制root不选，这样一来枚举两个root就可以了
}
}
}
void work(
int x)
{
vis[x]=
1;
root=
x;
while(!
vis[fa[root]])
{
root=
fa[root];
vis[root]=
1;
}
dp(root);
ll tmp=max(DP[root][
0],DP[root][
1]);
vis[root]=
1;
root=
fa[root];
dp(root);
ans+=max(tmp,max(DP[root][
0],DP[root][
1]));//对两个root分别处理，手推一下更容易理解
return;
}
int main()
{
n=
read();
for(re
int i=
1;i<=n;++
i)
{
val[i]=
read();
y=
read();
add(y,i);
fa[i]=
y;
}
for(re
int i=
1;i<=n;++
i)
{
if(!
vis[i])
{
work(i);
}
}
printf("%lld",ans);
return 0;
}
转载于:https://www.cnblogs.com/Liuz8848/p/10833532.html
相关资源：JAVA上百实例源码以及开源项目
