题解 P1453 【城市环路】

· · 题解

题目链接：城市环路。

关于题目：一道比较显然的 基环树 上的 dp 题。

应用算法：树形 dp + 环形 dp。

写在前面：

$\qquad\!\!updata\ \ 2020.10.6$：修改了之前挂错的链接；增加时空复杂度分析。 $\qquad\!\!updata\ \ 2020.10.25$：修改了之前对于 环形 dp 的初始化的一个错误。感谢 @[pigstd](https://www.luogu.com.cn/user/141179) 指出。 #### 下面进入正文： - 一、分析题意： $\qquad\!\!n$ 个点 $n$ 条边、全部联通且只有一个环，满足这些条件的图很显然是一棵[基环树](https://www.luogu.com.cn/blog/user52918/qian-tan-ji-huan-shu)。 $\qquad\!\!$每个点有点权且任意相邻的两个点不能同时选取，很显然我们需要进行类似于[没有上司的舞会](https://www.luogu.com.cn/problem/P1352)的 dp。 - 二、dp 过程： $\qquad\!\!$和其它题解不一样的，我的 dp 过程主要是利用基环树的一个性质将该问题分解为两个子问题逐一解决。 $\qquad\!\!$由于一棵基环树可以看作一棵树加了一条非重边在图上形成了唯一一个环，那么我们可以将该环上的每个点看作一个**根节点**，在不考虑环上的点与之联通的情况下，每个根节点都联通出**一棵树**。也就是说，一棵基环树等价于**很多棵树的根节点被连在了一个环上的一张图**。 $\qquad\!\!$由此，我们便可以将这个问题分解为**以环上的点为根节点的很棵多树的 树形 dp $+$ 这些环上的点的 环形 dp**。 $\qquad\!\!$具体过程如下： - 1、找环： $\qquad\!\!$我利用的是拓扑排序 $+$ dfs 的方式进行找环。 $\qquad\!\!$首先，对于所有节点拓扑排序一遍，而后入度为 $2$ 的点就是环上的点。 $\qquad\!\!$其次，任意选择一个环上的点（我选择的就是编号最小的节点）进行 dfs。 $\qquad\!\!$最后，每次 dfs 到一个 **未被记录入环并且入度为 $2$ 的节点**，将其记录入环并进行递归。 $\qquad\!\!$可能有同学要问：为什么不能直接拓扑排序后每个点一次循环一遍入度为 $2$ 就记录入环而要区 dfs 呢？ $\qquad\!\!$那是因为我们之后需要进行 环形 dp，需要保证**环上依次连续的点在图上也是依次连续的**，所以不能只进行一个简简单单的循环而需要 dfs。 - 2、树形 dp： $\qquad\!\!$即对于每棵树都进行一次[没有上司的舞会](https://www.luogu.com.cn/problem/P1352)的 dp 过程： $\qquad\!\!$设 $f_{i,0}$ 表示 $i$ 点不选择，$i$ 点子树的最大贡献；$f_{i,1}$ 表示 $i$ 点选择，$i$ 点子树的最大贡献。对于每个点 $i$，$f_{i,0}$ 的初始值为 $0$，$f_{i,1}$ 的初始值即为题目中的每个点的人流量 $p_i$。 $\qquad\!\!$转移方程（$v$ 点为 $u$ 点的子节点）： $\qquad\!\!f_{u,0}\gets f_{u,0}+\max(f_{v,0},f_{v,1}) 
$\qquad\!\!f_{u,1}\gets f_{u,1}+f_{v,0}$

- 3、环形 dp：

$\qquad\!\!$_没有接触过 环形 dp 的同学可以左转先看一下这两道题：[P6064 [USACO05JAN]Naptime G](https://www.luogu.com.cn/problem/P6064) 和 [SP283 NAPTIME - Naptime](https://www.luogu.com.cn/problem/SP283)。_

$\qquad\!\!$由于此时每棵树内部节点的关系均已满足题目的限定，剩下的就是环上的各个节点之间的关系，那么我们只需要对每棵树的根节点进行一次 环形 dp 即可得出答案。

$\qquad\!\!$设 $c_i$ 为环上第 $i$ 个点的编号，$tot$ 为环上的节点总数。

$\qquad\!\!$那么此时 $f_{c_i,0}$ 代表以 $c_i$ 为根的树不选 $c_i$ 最大贡献； $f_{c_i,1}$ 代表以 $c_i$ 为根的树选 $c_i$ 最大贡献。

$\qquad\!\!$设 $g_{i,0}$ 表示点 $c_i$ 不选，前 $i$ 个节点的最大贡献，设 $g_{i,1}$ 表示点 $c_i$ 选，前 $i$ 个节点的最大贡献。

$\qquad\!\!$转移方程：

$\qquad\!\!g_{i,0}\gets \max(g_{i-1,0},g_{i-1,1})+f_{c_i,0}$

$\qquad\!\!g_{i,1}\gets g_{i-1,0}+f_{c_i,1}$

$\qquad\!\!$由于是进行 环形 dp，为了枚举全面所有的情况，我们需要进行两次 dp 过程：

$\qquad\!\!$①、规定 $c_1$ 节点一定不选：

$\qquad\!\!\qquad\!\!$初始化 $g$ 中的每一个元素为 $-inf$；$g_{1,0}=f_{c_1,0}$。

$\qquad\!\!\qquad\!\!$进行 dp，统计答案 $ans=\max(g_{tot,0},g_{tot,1})$。

$\qquad\!\!$②、规定 $c_1$ 节点一定选：

$\qquad\!\!\qquad\!\!$初始化 $g$ 中的每一个元素为 $-inf$；$g_{1,1}=f_{c_1,1}$。

$\qquad\!\!\qquad\!\!$进行 dp，统计答案 $ans=\max(ans,g_{tot,0})$。
//P1453 城市环路
#include<bits/stdc++.h>
#define in inline
#define re register
#define N 100010
using namespace std;
int n;
int cnt,head[N];
struct edge
{
    int to,nxt;
};
edge e[N<<1];
bool b[N];
int tot;
int rd[N],c[N];
int f[N][2],g[N][2];
int ans;
double k;
in int qread()
//快读
{
    int x=0,y=1;
    int ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            y=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*y;
}
in void mr(re int u,re int v)
//建边
{
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
    return ;
}
in void dfs0(re int u,re int fa)
//找环
{
    for(re int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        //父节点或已在环上就不算
        if(v==fa||b[v])
        {
            continue;
        }
        //找到一个点就加入环
        if(rd[v]==2)
        {
            b[v]=1;
            c[++tot]=v;
            //递归
            dfs0(v,u);
            //加入一个点后就跳出循环
            break;
        }
    }
    return ;
}
in void tppx()
//拓扑排序
{
    queue<int> q;
    for(re int i=1;i<=n;i++)
    {
        if(rd[i]==1)
        {
            q.push(i);
        }
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(re int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            rd[v]--;
            if(rd[v]==1)
            {
                q.push(v);
            }
        }
    }
    for(re int i=1;i<=n;i++)
    {
        //找到第一个在环上的点加入环并进行 dfs
        if(rd[i]==2)
        {
            b[i]=1;
            c[++tot]=i;
            dfs0(i,0);
            //加入一个点后就跳出循环
            break;
        }
    }
    return ;
}
in void dfs(re int u,re int fa)
//树形 dp
{
    for(re int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(v==fa||b[v])
        //父节点或已在环上就不算
        {
            continue;
        }
        dfs(v,u);
        //转移
        f[u][0]+=max(f[v][1],f[v][0]);
        f[u][1]+=f[v][0];
    }
    return ;
}
int main()
{
    //读入
    n=qread();
    for(re int i=1;i<=n;i++)
    {
        f[i][1]=qread();
    }
    for(re int i=1;i<=n;i++)
    {
        int u=qread()+1;
        int v=qread()+1;
        //统计入度
        rd[u]++;
        rd[v]++;
        //建边
        mr(u,v);
        mr(v,u);
    }
    //拓扑排序
    tppx();
    //对于每棵树 树形 dp
    for(re int i=1;i<=tot;i++)
    {
        dfs(c[i],0);
    }
    //环形 dp
    memset(g,-0x3f,sizeof(g));
    g[1][0]=f[c[1]][0];
    for(re int i=2;i<=tot;i++)
    {
        g[i][1]=g[i-1][0]+f[c[i]][1];
        g[i][0]=max(g[i-1][0],g[i-1][1])+f[c[i]][0];
    }
    ans=max(g[tot][0],g[tot][1]);
    memset(g,-0x3f,sizeof(g));
    g[1][1]=f[c[1]][1];
    for(re int i=2;i<=tot;i++)
    {
        g[i][1]=g[i-1][0]+f[c[i]][1];
        g[i][0]=max(g[i-1][0],g[i-1][1])+f[c[i]][0];
    }
    ans=max(ans,g[tot][0]);
    //读入 k
    scanf("%lf",&k);
    //输出答案
    printf("%.1lf\n",ans*k);
    return 0;
}