洛谷 P1453 城市环路

发表于   |   分类于 洛谷 , 刷题   |   暂无评论

url: https://www.luogu.com.cn/problem/P1453

tag:
动态规划，图论，基环树，树形DP

思路：
基环树是一种特殊的图结构，可以看作是在一棵树的基础上加入一条额外的边，从而使图中恰好出现一个环，也称作单环图或唯一环图（unicyclic graph）。其主要特点包括：

  1. 连通性：基环树是连通图，任意两个顶点之间都有路径相连。
  2. 唯一的环：整个图中仅存在一个简单环，其他部分均保持树的结构（即无环）。
  3. 分解思想：可以将基环树看作由一个环和附着在环上各个顶点上的若干棵树构成。对于很多算法（例如树形 DP），通常先对环进行特殊处理（比如“断环”），再处理附着的树结构。

这种结构在算法竞赛中经常出现，处理时通常需要先找出环，然后考虑两种或多种情况（例如环上某些节点选或不选），从而在保证整体方案最优的前提下完成状态转移和求解。

这道题目其实和求树的最小覆盖问题类似，我们用 f[u][0/1] 表示节点u为根且选或者不选时的总共人流量。只是因为有基环树，所以需要先断边，然后分别用那一边的两个点为根且不选（方便另外一个点可选）时各跑一遍dfs，求答案，最后两个答案求一个最大值并乘上k，注意，对于不同的情况来说需要先将f数组清空（因为可选的点不同了）。

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int h[N], e[N * 2], ne[N * 2], idx;
int p[N];
bool st[N];
double k;
int n, s1, s2, flag;
int f[N][2];
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}
void dfs1(int u, int fa)
{
    st[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int v = e[i];
        if (v == fa) continue;
        if (st[v])
        {
            s1 = u, s2 = v;
            flag = true;
            return;
        }
        dfs1(v, u);
        if (flag) return ;
    }
    st[u] = 0;
}
void dfs2(int u, int fa)
{
    f[u][1] = p[u];
    for (int i = h[u]; ~i; i = ne[i])
    {
        int v = e[i];
        if (v == fa) continue;
        if ((u == s1 && v == s2) || (u == s2 && v == s1)) continue;
        dfs2(v, u);
        f[u][1] += f[v][0];
        f[u][0] += max(f[v][0], f[v][1]);
    }
}
int main()
{
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> p[i];
    int a, b;
    for (int i = 0; i < n; i ++)
    {
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    cin >> k;
    dfs1(0, 0);
    dfs2(s1, s1);
    int res1 = f[s1][0];
    memset(f, 0, sizeof f);
    dfs2(s2, s2);
    int res2 = f[s2][0];
    printf("%.1f", max(res1, res2) * k);
    return 0;
}
添加新评论