P1453 城市环路 题解

xcxc82 · 2020-08-03 22:05:37 · 题解

P1453 城市环路 题解

间隙

前置知识

• 树形dp,基环树

大致题意

给一颗含有点权的基环外向树

假如两个点之间有一条边连接,如果选择了其中一端的节点,那另一段的节点则不可选择

求:最大贡献

分析

先讲一下什么是基环树。

基环树,简单来说就是多了一条边的树,产生了一个环形结构,环上的每个节点都是一颗树的根

画成图的话大概是这个样子(基环外向树)

一般来说,这种题目的做法都是先找到环,断开环中的一条边, 把它当成一般的树形DP来做。

如何找环?

一般有dfs跟并查集两种方法 , 这里我采用的是并查集的做法

一开始每个节点都是一个独立的集合

每连接一条边,就把这两个点合并到一个集合中

如果在连接一条边之前,两个节点就已经在一个集合中了,说明这两个节点已经联通了,再连接这条边必然会产生环的情况

如何转移?

找到了环之后,只需要将环上的这条边断开即可

这样的话就可以当作普通的树形DP来做了

设f[i][0]为选第i个节点产生的最大贡献

代码实现

思路明白了代码实现应该就不难了

要注意的是环上的两个点都可以作为树的根节点,因此在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;
}