「KTSC 2023 R1」外环道路 2题解

问题分析

本题要求我们在一个特殊的树结构（加上外环边后形成平面图）中，找到覆盖所有奇数长度简单环的最小代价边集。这是一个奇环覆盖问题，在图论中可以通过转化为最大权匹配来解决。

关键思路

1. 图的结构特性

• 原图是一棵树，加上外环边后形成一个平面图
• 叶子节点按顺序连接形成外环
• 交叉路口的编号具有特殊的遍历顺序性质

2. 算法核心

将问题转化为在对偶图上求最大权匹配：

• 每个面（包括外表面）对应一个节点
• 每条边连接两个面，权重为原边权重
• 覆盖所有奇环等价于在对偶图中选择边集，使得每个奇面至少有一条相邻边被选
• 这可以转化为最大权匹配问题

3. 动态规划解法

由于树的特殊结构，我们可以使用树形DP来求解：

ll dp[mxn][2][2][2];
// dp[v][a][b][c] 表示在节点v的子树中：
// a: 父边是否被选
// b: 最左侧叶子对应的外环边状态  
// c: 最右侧叶子对应的外环边状态
// 的最大权重和

代码详解

预处理阶段

void dfs(int v) {
    sort(all(adj[v]));  // 按编号排序，满足题目性质
    
    for (auto u : adj[v]) {
        dfs(u.f);  // 递归处理子树
    }
    
    // 记录叶子节点的环上位置
    if (adj[v].empty()) {
        id[v] = cnt++;
        lc[v] = rc[v] = v;
    } else {
        lc[v] = lc[adj[v][0].f];    // 最左叶子
        rc[v] = rc[adj[v].back().f]; // 最右叶子
    }
}

动态规划转移

void dfs1(int v) {
    if (adj[v].empty()) {
        // 叶子节点初始化
        dp[v][0][0][0] = 0;
        dp[v][1][1][1] = 0;
        return;
    }
    
    // 处理第一个子节点
    int u = adj[v][0].f;
    ll d = adj[v][0].s;
    
    for (int a = 0; a < 2; a++) {
        for (int b = 0; b < 2; b++) {
            for (int c = 0; c < 2; c++) {
                // 选择或不选择连接到第一个子节点的边
                dp[v][a][b][c] = max(dp[u][a][b][c], 
                                    dp[u][a^1][b][c] + d);
            }
        }
    }
    
    // 依次合并其他子节点
    int cur = id[rc[u]];
    for (int i = 1; i < (int)adj[v].size(); i++) {
        int u = adj[v][i].f;
        ll D = adj[v][i].s;
        
        ll dp1[2][2][2];
        // 状态转移：考虑子节点间的外环边
        for (int a = 0; a < 2; a++) {
            for (int b = 0; b < 2; b++) {
                for (int c = 0; c < 2; c++) {
                    dp1[a][b][c] = -inf;
                    for (int d = 0; d < 2; d++) {
                        for (int e = 0; e < 2; e++) {
                            for (int f = 0; f < 2; f++) {
                                ll val = dp[v][a][b][d] + dp[u][f][e][c] 
                                       + D * ((a != f) ? 1 : 0)  // 当前边
                                       + w[cur] * ((d != e) ? 1 : 0); // 外环边
                                dp1[a][b][c] = max(dp1[a][b][c], val);
                            }
                        }
                    }
                }
            }
        }
        
        // 特殊处理根节点的最后一个子节点（连接首尾）
        if (v == 0 && i == (int)adj[v].size() - 1) {
            for (int a = 0; a < 2; a++) {
                for (int b = 0; b < 2; b++) {
                    for (int c = 0; c < 2; c++) {
                        if (b != c) dp1[a][b][c] += w.back();
                    }
                }
            }
        }
        
        memcpy(dp[v], dp1, sizeof(dp1));
        cur = id[rc[u]];
    }
}

主函数

long long place_police(vector<int> P, vector<long long> C, vector<long long> W) {
    // 初始化
    int n = (int)P.size() + 1;
    w = W;
    
    // 建图
    for (int i = 0; i < (int)P.size(); i++) {
        adj[P[i]].push_back({i + 1, C[i]});
    }
    
    // DP求解最大权重
    dfs(0);
    dfs1(0);
    
    ll mx = -inf;
    for (int a = 0; a < 2; a++) {
        for (int b = 0; b < 2; b++) {
            for (int c = 0; c < 2; c++) {
                mx = max(mx, dp[0][a][b][c]);
            }
        }
    }
    
    // 总权重减去最大匹配权重即为最小覆盖代价
    ll sum = 0;
    for (auto v : C) sum += v;
    for (auto v : W) sum += v;
    
    return sum - mx;
}

复杂度分析

• 时间复杂度：$O(N)$，每个节点处理一次
• 空间复杂度：$O(N)$，存储树结构和DP状态

算法正确性

该解法利用了树的特殊结构和平面图的性质，通过动态规划巧妙地处理了：

$1.$ 树边的选择

$2.$ 外环边的选择

$3.$ 奇环覆盖的约束条件

最终将最小覆盖问题转化为最大权匹配问题，得到了最优解。