1 条题解

  • 0
    @ 2025-10-8 16:49:10
    #include <bits/stdc++.h>
    using namespace std;
    const int N=1600;
    vector<int> G[N];
    int f[N][2][2];
    /*
        这里的  安全 表示以x为根的子树全部都安全
              不安全 表示以x为根的子树除了x都安全
        f[x][0][0]表示 x这个点 不安全,不派人,   
        f[x][0][1]表示 x这个点 不安全,  派人,   ———很明显不合理所以去除 
        f[x][1][0]表示 x这个点   安全,不派人,   
        f[x][1][1]表示 x这个点   安全,  派人,    
    */
    void dp(int x, int fa)
    {
        f[x][1][1] = 1; f[x][1][0] = 0;
        for(int y : G[x]) if(y != fa)
        {
            dp(y, x);
            f[x][1][0] += f[y][1][1];
            f[x][1][1] += min(f[y][1][0], f[y][1][1]);
        }
    }
    int main()
    {
        int n;
        while(scanf("%d", &n) != EOF)
        {
            memset(G, 0, sizeof(G));
            for(int i=1, x, m; i <= n; i++)
            {
                scanf("%d:(%d)", &x, &m);
                for(int j=1, y; j <= m; j++)
                {
                    scanf("%d", &y);
                    G[x].emplace_back(y);
                    G[y].emplace_back(x);
                }
            }
            int rt = 1;
            dp(rt, -1);
            printf("%d\n", min(f[rt][1][0], f[rt][1][1]));
        }
        return 0;
    }
    
    • 1

    *【树形DP:相邻点兼容】保护所有边[战略游戏]

    信息

    ID
    304
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    递交数
    290
    已通过
    34
    上传者