P1453 城市环路 题解
间隙
前置知识
-
树形dp,基环树
大致题意
给一颗含有点权的基环外向树
假如两个点之间有一条边连接,如果选择了其中一端的节点,那另一段的节点则不可选择
求:最大贡献
分析
先讲一下什么是基环树。
基环树,简单来说就是多了一条边的树,产生了一个环形结构,环上的每个节点都是一颗树的根
画成图的话大概是这个样子(基环外向树)
一般来说,这种题目的做法都是先找到环,断开环中的一条边,
把它当成一般的树形(DP)来做。
如何找环?
一般有(dfs)跟并查集两种方法 , 这里我采用的是并查集的做法
一开始每个节点都是一个独立的集合
每连接一条边,就把这两个点合并到一个集合中
如果在连接一条边之前,两个节点就已经在一个集合中了,说明这两个节点已经联通了,再连接这条边必然会产生环的情况
如何转移?
找到了环之后,只需要将环上的这条边断开即可
这样的话就可以当作普通的树形(DP)来做了
设(f[i][0])为选第(i)个节点产生的最大贡献
(f[i][1])为不选第(i)个节点产生的最大贡献
如果选了第(i)个节点,那它的儿子肯定都不能选
反之,儿子可以选择选,也可以选择不选
得到转移方程:
(f[u][0] = sum f[v][0])
(f[u][1] = sum max(f[v][1],f[v][0]))
代码实现
思路明白了代码实现应该就不难了
要注意的是环上的两个点都可以作为树的根节点,因此在(DP)的时候要把两个点都跑一遍
具体的细节注释有写
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+10;
struct edge{//存图
int v,next;
}e[MAXN<<1];
int f[MAXN][2],w[MAXN];//dp数组,点权
double k;
int fa[MAXN];
int head[MAXN<<1],cnt = 0;
int root1,root2;//环上的两个点
int n;
void add(int u,int v){//前向星
e[++cnt].v = v;
e[cnt].next = head[u];
head[u] = cnt;
}
int find(int x){//查找集合
if(fa[x]==x){
return x;
}
else{
return fa[x] = find(fa[x]);
}
}
void circle(int u,int fa){//树形dp
f[u][1] = w[u],f[u][0] = 0;//初始化
for(int i=head[u];i;i=e[i].next){
int v = e[i].v;
if(v!=fa){
circle(v,u);
f[u][0]+=max(f[v][1],f[v][0]);//转移
f[u][1]+=f[v][0];
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
fa[i] = i;//初始化集合
}
for(int i=1;i<=n;i++){
int u,v;
scanf("%d%d",&u,&v);
u++,v++;
if(find(u)==find(v)){//如果在加边前就在一个集合中了,说明找到了环
root1 = u,root2 = v;//记录环上的两个点
continue;//直接跳过加边操作,相当于断开这条边
}
add(u,v);
add(v,u);
fa[find(v)] = find(u);//合并集合
}
scanf("%lf",&k);
circle(root1,0);
double r1 = f[root1][0];//选root1
circle(root2,0);
double r2 = f[root2][0];//选root2
printf("%.1lf",max(r1,r2)*k);//取最大
return 0;
}