题目描述

消防员需要在城市中铺设消防栓。城市的道路可以看作是一棵连通且无回路的树，每个节点代表一个底座，边代表道路。

1.消防栓必须安装在底座上 => 消防栓只能放置在树的节点上

2.每条道路必须有消防栓盖 => 任何一条边都需要满足：所连接的两个节点至少有一个节点上有消防栓。

3.交叉路口只有一个消防栓底座，可以覆盖所有连接的道路 =》 每个节点最多放置一个消防栓，放置了就可以覆盖所有其他节点。

4.求覆盖所有道路所需的最少消防栓数量。 =》

给定一棵树，求选出最少的节点集合$set$ , 使得a:每一个节点至少有一个邻居属于集合$set$，且b:任意一条边所连接的两个节点至少有一个节点属于集合$set$。

我们发现b 包含a 。 所以就是：给定一棵树，求选出最少的节点集合$set$ , 使得任意一条边所连接的两个节点至少有一个节点属于集合$set$。

思路

要解决这个问题，最终我们需要将其转化为树的最小顶点覆盖问题，并利用动态规划进行高效求解。具体而言，对树进行深度优先搜索（DFS），为每个节点维护两个状态：选中该节点（铺设消防栓）和不选中该节点。若选中当前节点，其子节点可以选择或不选择，取最小值；若不选中当前节点，则所有子节点必须被选中以覆盖相应的道路。通过这种方式深入分析每个节点的最优选择，最终在根节点处得到覆盖所有道路所需的最少消防栓数量。

• 通过 DFS 遍历树，并计算每个节点的 dp 值。
  • dp[u][1] 表示节点 u 被选中，其值为 1 加上所有子节点的最小覆盖数（子节点可以选或不选，取最小值）。
  • dp[u][0] 表示节点 u 不被选中，其值为所有子节点必须被选中的覆盖数。

最终答案就是$min(dp[0][0],dp[0][1])$

cpp

#include <bits/stdc++.h>
using namespace std;

// 定义最大节点数
const int MAX = 1505;

// 全局变量
vector<vector<int>> adj(MAX); // 邻接表
int dp_val[MAX][2]; // dp[u][0]: u不被选中, dp[u][1]: u被选中
bool visited_flag[MAX]; // 访问标记

// 深度优先搜索计算dp值
int dfs(int u) {
    visited_flag[u] = true;
    dp_val[u][0] = 0; // u不被选中时，初始化为0
    dp_val[u][1] = 1; // u被选中时，初始化为1
    for(auto &v: adj[u]){
        if(!visited_flag[v]){
            dfs(v); // 递归计算子节点
            dp_val[u][1] += min(dp_val[v][0], dp_val[v][1]); // u被选中，子节点可选或不选，取最小值
            dp_val[u][0] += dp_val[v][1]; // u不被选中，子节点必须被选中
        }
    }
    return min(dp_val[u][0], dp_val[u][1]); // 返回当前节点的最小覆盖数
}

int main(){
    // 优化输入速度
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    // 读取直到文件结束（处理多组测试用例）
    while(cin >> n){
        // 清空邻接表
        for(int i=0;i<n;i++) adj[i].clear();
        // 读取n行描述
        for(int i=0;i<n;i++){
            string line;
            cin >> ws; // 读取前导空格
            getline(cin, line);
            // 解析格式 a:(b) x1 x2 ... xb
            int a, b;
            size_t pos1 = line.find(":(");
            a = stoi(line.substr(0, pos1));
            size_t pos2 = line.find(")", pos1);
            b = stoi(line.substr(pos1+2, pos2 - pos1 -2));
            // 读取后面的b个数字
            if(b > 0){
                size_t start = pos2 + 1;
                // 提取子节点编号
                while(start < line.size() && line[start] == ' ') start++; // 跳过空格
                string nums = line.substr(start);
                // 分割数字
                int v;
                stringstream ss(nums);
                while(ss >> v){
                    adj[a].push_back(v);
                    adj[v].push_back(a); // 无向图
                }
            }
        }
        // 重置访问标记
        fill(visited_flag, visited_flag + n, false);
        // 处理极端情况：只有一个节点
        if(n == 1){
            cout << "1\n";
            continue;
        }
        // 假设根节点为0
        cout << dfs(0) << "\n";
    }
}

java

import java.util.*;
import java.io.*;

public class Main {
    static int n;
    static ArrayList<ArrayList<Integer>> adj;
    static int[][] dp;
    static boolean[] visited;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        // 读取直到文件结束（处理多组测试用例）
        while((line = br.readLine()) != null){
            line = line.trim();
            if(line.equals("")) continue;
            n = Integer.parseInt(line);
            adj = new ArrayList<>();
            for(int i=0;i<n;i++) adj.add(new ArrayList<>());
            // 读取n行描述
            for(int i=0;i<n;i++){
                String desc = br.readLine();
                if(desc == null || desc.trim().equals("")) continue;
                desc = desc.trim();
                int pos1 = desc.indexOf(":(");
                int a = Integer.parseInt(desc.substring(0, pos1));
                int pos2 = desc.indexOf(")", pos1);
                int b = Integer.parseInt(desc.substring(pos1+2, pos2));
                if(b > 0){
                    String connectionsStr = desc.substring(pos2+1).trim();
                    if(!connectionsStr.equals("")){
                        String[] connections = connectionsStr.split(" ");
                        for(int j=0; j<connections.length; j++){
                            if(connections[j].equals("")) continue;
                            int v = Integer.parseInt(connections[j]);
                            adj.get(a).add(v);
                            adj.get(v).add(a);
                        }
                    }
                }
            }
            // 初始化DP和访问数组
            dp = new int[n][2];
            visited = new boolean[n];
            // 处理特殊情况
            if(n == 1){
                System.out.println(1);
                continue;
            }
            // 递归计算
            dfs(0);
            // 输出结果
            System.out.println(Math.min(dp[0][0], dp[0][1]));
        }
    }

    // 深度优先搜索计算DP值
    static void dfs(int u){
        visited[u] = true;
        dp[u][0] = 0; // u不被选中
        dp[u][1] = 1; // u被选中
        for(int v : adj.get(u)){
            if(!visited[v]){
                dfs(v);
                dp[u][1] += Math.min(dp[v][0], dp[v][1]); // u被选中，子节点可选或不选，取最小值
                dp[u][0] += dp[v][1]; // u不被选中，子节点必须被选中
            }
        }
    }
}

python

import sys
from collections import defaultdict

# 定义最大节点数
MAX = 1505

# 全局变量
adj = defaultdict(list)  # 邻接表
dp_val = [[0] * 2 for _ in range(MAX)]  # dp[u][0]: u不被选中, dp[u][1]: u被选中
visited_flag = [False] * MAX  # 访问标记

# 深度优先搜索计算dp值
def dfs(u):
    visited_flag[u] = True
    dp_val[u][0] = 0  # u不被选中时，初始化为0
    dp_val[u][1] = 1  # u被选中时，初始化为1
    for v in adj[u]:
        if not visited_flag[v]:
            dfs(v)  # 递归计算子节点
            dp_val[u][1] += min(dp_val[v][0], dp_val[v][1])  # u被选中，子节点可选或不选，取最小值
            dp_val[u][0] += dp_val[v][1]  # u不被选中，子节点必须被选中
    return min(dp_val[u][0], dp_val[u][1])  # 返回当前节点的最小覆盖数

def main():
    input = sys.stdin.read
    data = input().strip().splitlines()
    idx = 0
    while idx < len(data):
        n = int(data[idx].strip())
        idx += 1
        
        # 清空邻接表
        adj.clear()
        
        for i in range(n):
            line = data[idx].strip()
            idx += 1
            # 解析格式 a:(b) x1 x2 ... xb
            pos1 = line.find(":(")
            a = int(line[:pos1])
            pos2 = line.find(")", pos1)
            b = int(line[pos1 + 2:pos2])
            # 读取后面的b个数字
            if b > 0:
                nums = line[pos2 + 1:].strip()
                neighbors = list(map(int, nums.split()))
                for v in neighbors:
                    adj[a].append(v)
                    adj[v].append(a)  # 无向图
        
        # 重置访问标记
        visited_flag[:] = [False] * n
        
        # 处理极端情况：只有一个节点
        if n == 1:
            print(1)
            continue
        
        # 假设根节点为0
        print(dfs(0))

if __name__ == "__main__":
    main()

题目内容

消防员正在给城市铺设消防栓，城市的道路可以看作一个连通且无回路的图，每条道路有两个底座，消防栓必须铺设在底座上，每条道路必须有消防栓盖；交叉路口只有一个消防栓底座；交叉路口的消防栓可以覆盖连接的所有道路，求至少需要多少个消防栓才能覆盖城市所有的道路?

输入描述

每个 $case$ ，第一行一个整数 $n$ ，表示底座数。($1<=n<=1500$)

接下来 $n$ 行，每行以 $a:(b)$ 这样的格式开头，$a$ 表示底座的编号($0<=a<=n-1$), $b$ 表示与该底座相连接的底座数，接下来 $b$ 个数，表示与该底座相连的底座编号。

输出描述

一个数字，为需要的消防栓的最少个数

样例1

输入

3
0:(2) 1 2
1:(0)
2:(0)

输出

1

说明

$0$ 号底座与 $1$ 号和 $2$ 号相连，那么只需要在 $0$ 号铺设一个消防栓即可覆盖所有的道路，如下图所示：

样例2

输入

8
0:(3) 1 2 3
1:(1) 6
2:(0)
3:(0)
6:(1) 7
7:(2) 4 5
4:(0)
5:(0)

输出

3

说明

如图所示，在绿色节点上铺设消防栓即可覆盖全部道路

提示

动态规划