基环树算法总结
一、什么是基环树
基环树,顾名思义,有两个要素:环和树。
因此,基环树就是一棵树的一个节点,扩成一个环,做题时,多棵基环树组成的基环树森林,常以如下方式出现:
- 每个点只有一个出边。
- 每个点只有一个入边。
- 图中一共有 \(n\) 个点,\(n\) 条边。
那么,基环树类型的题目应该怎么做呢?
二、基环树怎么做
先来看看这道题:\([ZJOI2008]\) 骑士
此题和没有上司的舞会几乎一模一样,不一样的是,这道题是基环树。
考虑假如这道题在树上就会简单很多,那么我们就会发现,假如断掉环上的一条边,那么原来的基环树就变成了一棵树,树形 dp 即可。
#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
int n,m,a,h[N],w[N];
int to[N*2],nxt[N*2];
int vis[N],fa[N];
int q1[N],q2[N],l,r;
ll dp1[N],dp2[N],ans;
void add(int x,int y){
to[++m]=y;
nxt[m]=h[x];
h[x]=m;
}void dp_(int x,int f,int rt){
vis[x]=1;
dp1[x]=0;
dp2[x]=w[x];
for(int i=h[x];i;i=nxt[i]){
int y=to[i];
if(y==a)
continue;
dp_(y,x,rt);
dp1[x]+=max(dp1[y],dp2[y]);
dp2[x]+=dp1[y];
}
}int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
int j;
cin>>w[i]>>j;
add(j,i);
fa[i]=j;
}for(int i=1;i<=n;i++){
if(vis[i]) continue;
vis[(a=i)]=1;
while(!vis[fa[a]]){
a=fa[a];
vis[a]=1;
}dp_(a,0,a);
ll cc=dp1[a];
a=fa[a];
dp_(a,0,a);
ans+=max(cc,dp1[a]);
}cout<<ans;
return 0;
}
接着我再介绍一下我求基环树(单向图)时常用的找环方法(其中 \(a_i\) 表示 \(i\) 的出/入边与 \(a_i\) 相连):
在进行并查集时,无条件将 \(i\) 置于 \(a_i\) 下。这样可以保证每个根节点都在环上,使判环更便捷、更迅速。
标签:总结,dp2,dp1,int,基环树,算法,这道题,dp From: https://www.cnblogs.com/chang-an-22-lyh/p/18147499/jhs_zj