洛谷P1453 城市环路 题解

题目链接：P1453 城市环路

题意：

整个城市可以看做一个 $n$ 个点，$n$ 条边的单圈图(保证图连通)，唯一的环便是绕城的环路。保证环上任意两点有且只有 $2$ 条简单路径互通。图中的其它部分皆隶属城市郊区。

现在，有一位名叫 Jim 的同学想在 B 市开店，但是任意一条边的 $2$ 个点不能同时开店，每个点都有一定的人流量，第 $i$ 个点的人流量是 $p_i$，在该点开店的利润就等于 $p_i×k$，其中 $k$ 是一个常数。

Jim 想尽量多的赚取利润，请问他应该在哪些地方开店？

• 对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$，$1 \leq p_i \leq 10^4$，$0 \leq u, v < n$，$0 \leq k \leq 10^4$，$k$ 的小数点后最多有 $6$ 位数字。

显然这是一个基环树dp

对于基环树dp，

基本思想就是在那个环上找两个相邻点

分别作为根节点跑树形dp

因为本题中这两个点不能同时选，所以这么做是可以得到正确答案的

转移方程太简单了，直接看代码吧

相信做这个题的不可能树形dp都不会吧。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)

struct Edge
{
    int u,v,next;
}e[N<<1];
int n,fa[N],f[N][2],p[N],head[N],pos=1,S,T;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void addEdge(int u,int v)
{
    e[++pos]={u,v,head[u]};
    head[u]=pos;
}
void dfs(int u,int Fa)
{
    f[u][1]=p[u];f[u][0]=0;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v=e[i].v;
        if(v==Fa)continue;
        dfs(v,u);
        f[u][0]+=max(f[v][0],f[v][1]);
        f[u][1]+=f[v][0];
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> p[i],fa[i]=i;
    for(int i=1,u,v; i<=n; i++)
    {
        cin >> u >> v;++u;++v;
        if(find(u)==find(v)){S=u,T=v;continue;}
        addEdge(u,v);addEdge(v,u);
        fa[find(u)]=find(v);
    }
    double k; cin >> k;
    dfs(S,0); int res=f[S][0];
    dfs(T,0); res=max(res,f[T][0]);
    cout << fixed << setprecision(1);
    cout << (double)res*k << '\n';
    return 0;
}