闫氏dp分析法

代码

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

public class Main{
    static int N = 1510,M = 300660;
    static int[] h = new int[N],e = new int[M],ne = new int[M];
    static int[][] f = new int[N][2];
    static boolean[] st = new boolean[N];
    static int idx = 0;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer sc = new StreamTokenizer(br);
        while(sc.nextToken()!=StreamTokenizer.TT_EOF){
            int n = (int)sc.nval;
            Arrays.fill(h,-1);
            Arrays.fill(st,false);
            for(int i = 1;i<=n;i++){
                sc.nextToken();
                int f = (int)sc.nval;
                sc.nextToken();
                sc.nextToken();
                sc.nextToken();
                int cnt = (int)sc.nval;
                sc.nextToken();
                for(int j = 1;j<=cnt;j++){
                    sc.nextToken();
                    int s = (int)sc.nval;
                    add(f,s);
                    st[s] = true;
                }
            }
            int root = 0;
            while(st[root]) root++;
            dfs(root);
            System.out.println(Math.min(f[root][0],f[root][1]));
        }
    }
    public 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][1] += Math.min(f[j][1],f[j][0]);
            f[u][0] += f[j][1];
        }
    }
    public static void add(int a,int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
}