P2016战略游戏题解

like1 · 2019-11-06 11:35:55 · 题解

本题是一道经典的最小边覆盖问题，也叫数的最大独立集；一定要和最大点覆盖区分（P3942将军令）

本题可以考虑树形DP；设f[x][1]表示x节点放置士兵时，以x为根的子树需要的最少士兵数；f[x][0]表示x节点不放置士兵时，以x为根的子树需要的最少士兵数。

则转移就为f[u][0]+=f[v][1];f[u][1]=max(f[v][1],f[v][0]);最后答案就为min(f[1][1],f[1][0])；

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

int n,x,y,z,tot;
int head[1501],f[1501][2];
struct Edge
{
    int to,next;
}edge[3001];

inline void addedge(int x,int y)
{
    ++tot;
    edge[tot].to=y;
    edge[tot].next=head[x];
    head[x]=tot;
}

inline void dfs(int u,int fa)
{
    f[u][1]=1;
    f[u][0]=0;
    if(head[u]==0) f[u][0]=100000000;
    for(int i=head[u];i;i=edge[i].next)
    {
        if(edge[i].to!=fa)
        {
            dfs(edge[i].to,u);
            f[u][1]+=min(f[edge[i].to][1],f[edge[i].to][0]);
            f[u][0]+=f[edge[i].to][1];
        }
    }   
}

int main( )
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        x++;
        for(int j=1;j<=y;j++)
        {
            scanf("%d",&z);
            z++;
            addedge(x,z);
            addedge(z,x);
        }
    }
    dfs(1,0);
    printf("%d",min(f[1][1],f[1][0]));
} 

最后祝大家CSP2019rp++,score++;