算法分析

树形dp，与没有上司的舞会具有对称性

没有上司的舞会题解地址https://www.acwing.com/solution/acwing/content/7920/

• 没有上司的舞会：每条边上最多选择一个点，求最大权值

• 战略游戏：每条边上最少选择一条点，求最小权值

状态表示

• f[u][0]：所有以u为根的子树中选择，并且不选u这个点的方案

• f[u][1]：所有以u为根的子树中选择，并且选u这个点的方案

• 属性：Min

状态计算

当前u结点不选，子结点一定选

• $f[u][0] = \sum (f[s_i,1])$

当前u结点选，子结点一定可选可不选

• $f[u][1] = \sum min(f[s_i,0],f[s_i,1])$

时间复杂度 $O(n)$

参考文献

算法提高课,感谢 @mxyzptlk13 大佬的指点

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main{
    static int N = 1510;
    static int M = N;
    static int n;
    static int m;
    static int[][] f = new int[N][2];
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int idx = 0;
    static boolean[] st = new boolean[N];
    static void add(int a,int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    static void dfs(int u)
    {
        f[u][1] = 1;f[u][0] = 0;
        for(int i = h[u];i != -1;i = ne[i])
        {
            int j = e[i];
            dfs(j);

            f[u][0] += f[j][1];
            f[u][1] += Math.min(f[j][1], f[j][0]);
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true)
        {
            String str = br.readLine();
            if (str == null) break;
            int n = Integer.parseInt(str);
            Arrays.fill(h, -1);
            Arrays.fill(st, false);
            idx = 0;
            while(n -- > 0)
            {
                String[] s = br.readLine().split(" ");
                int a = Integer.parseInt(s[0].substring(0, s[0].indexOf(':')));
                if(s.length > 1)
                {
                    for(int i = 1;i < s.length ;i ++)
                    {
                        int b = Integer.parseInt(s[i]);
                        add(a,b);
                        st[b] = true;
                    }
                }
            }
            int root = 0;
            while(st[root]) root ++;
            dfs(root);
            System.out.println(Math.min(f[root][0], f[root][1]));
        }
    }
}