题目描述

塔子哥组织小朋友们在玩一场小游戏, 一共有$n$个小朋友, 编号为$0 ... n-1$, 每个小朋友身后都有一根绳子, 一个小朋友可以不拿或者拿多个同学的绳子, 拿完之后塔子哥会让小朋友们保持不动, 给小朋友发糖果。

给一个小朋友分糖果, 他就会开心, 否则他就会不开心。

可是塔子哥的糖果没有很多了, 怎么分才能使最少的糖果让每个绳子两头都最少有一个开心的小朋友呢

(一个小朋友只能被一个小朋友牵, 一个小朋友可以牵多个小朋友, 最终类似一个树形结构, 题目保证所有小孩子都牵了人或者被人牵)

输入描述

第一行一个整数$n$，表示小朋友数量$(1\le n\le 1500)$ 接下来$n$行，每行以$a:(b)$ 这样的格式开头，$a$表示小朋友的编号$(0\le a\le n-1)$ $b$表示第$i$个小朋友牵了几个小朋友,接下来$b$个数，表示被牵的小朋友的编号

输出描述

一个数字，为需要的糖果的最少个数

样例

输入1

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

输出1

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)

输出2

3

说明 给 0, 6, 7号小朋友发糖果, 就可使得所有绳子两端都有开心的小朋友

题面描述

塔子哥组织了一场小朋友的游戏，需要分发糖果以确保每根绳子的两端至少有一个小朋友开心。每个小朋友可以牵引多个同学，形成树形结构。通过合理分配糖果，目标是用最少的糖果让每个小朋友开心，从而实现快乐的游戏氛围。输入包含小朋友数量及其牵引关系，输出所需的最少糖果数。

思路：树形DP

定义$f[i][j]$为以$i$为结点的子树中，不放消防栓/放消防栓（$j=0/1$）的最小个数

如果在第$i$个结点放置消防栓，那么对于结点$i$的所有子节点，都可以放置/不放置消防栓

则有$f[i][1]=\sum_{}^{}min(f[u][0],f[u][1]) (u\in {i|u是i的子节点})$

如果在第$i$个结点不放置消防栓，那么对于结点$i$的所有子节点，都必须要放置消防栓

则有$f[i][0]=\sum_{}^{}f[u][1] (u\in {i|u是i的子节点})$

代码分析

这段代码的目的是在树形结构中找到最优的消防栓放置策略，以最小化需要的消防栓数量。以下是代码的详细分析：

1. 变量与数据结构的初始化：

   • const int N = 1510;：定义最大节点数为1510。
   • int n;：小朋友数量，即树的节点数量。
   • vector<vector<int>> g;：邻接表，用于存储树的结构。
   • int f[N][2];：动态规划数组，其中 f[i][0] 表示不在节点 i 放置消防栓时的最小数量，f[i][1] 表示在节点 i 放置消防栓时的最小数量。
   • int d[N];：入度数组，用于记录每个节点的入度，以便找到根节点。

2. 深度优先搜索（DFS）函数：

   • void dfs(int u)：递归函数，遍历树的节点。
     • 初始化 f[u][1] = 1，表示当前节点放置消防栓的数量。
     • 初始化 f[u][0] = 0，表示当前节点不放置消防栓时的数量。
     • 对于每个子节点 x，递归调用 dfs(x)。
     • 更新状态转移方程：如果放置消防栓，子节点可以选择放或不放；如果不放，则子节点必须放置。

C++

#include<bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>>g;
const int N=1510;
int f[N][2],d[N];
void dfs(int u)
{
    f[u][1]=1;f[u][0]=0;
    for(int &x:g[u])
    {
        dfs(x);
        f[u][1]+=min(f[x][0],f[x][1]);
        f[u][0]+=f[x][1];
    }
    
}
int main()
{
    cin>>n;
    g.resize(n);
    memset(d,0,sizeof d);
    int t,cnt;
    for(int i=0;i<n;i++)
    {
        scanf("%d:(%d)",&t,&cnt);
        while(cnt--)
        {
            int a;
            cin>>a;
            g[t].push_back(a);
            d[a]++;
        }
    }
    int root=0;
    while(d[root])root++;
    dfs(root);
    int res=min(f[root][0],f[root][1]);
    cout<<res<<endl;
    return 0;
}

Java

import java.util.*;

public class Main {
    static int n;
    static List<List<Integer>> g;
    static final int N = 1510;
    static int[][] f = new int[N][2];
    static int[] d = new int[N];

    static void dfs(int u) {
        f[u][1] = 1;
        f[u][0] = 0;
        for (int x : g.get(u)) {
            dfs(x);
            f[u][1] += Math.min(f[x][0], f[x][1]);
            f[u][0] += f[x][1];
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        g = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            g.add(new ArrayList<>());
        }
        Arrays.fill(d, 0);
        for (int i = 0; i < n; i++) {
            String[] data = sc.next().split(":");
            int t = Integer.parseInt(data[0]);
            int cnt = Integer.parseInt(data[1].substring(1, data[1].length() - 1));
            while (cnt-- > 0) {
                int a = sc.nextInt();
                g.get(t).add(a);
                d[a]++;
            }
        }
        int root = 0;
        while (d[root] > 0) {
            root++;
        }
        dfs(root);
        int res = Math.min(f[root][0], f[root][1]);
        System.out.println(res);
    }
}

Python

import re

n = int(input())
g = [[] for _ in range(n)]
N = 1510
f = [[0, 0] for _ in range(N)]
d = [0 for _ in range(N)]

def dfs(u):
    f[u][1] = 1
    f[u][0] = 0
    for x in g[u]:
        dfs(x)
        f[u][1] += min(f[x][0], f[x][1])
        f[u][0] += f[x][1]

for _ in range(n):
    data = re.findall(r'\d+', input())
    t = int(data[0])
    cnt = int(data[1])
    for i in range(2, 2 + cnt):
        a = int(data[i])
        g[t].append(a)
        d[a] += 1

root = 0
while d[root] > 0:
    root += 1

dfs(root)
res = min(f[root][0], f[root][1])
print(res)