Loading...

战略游戏 洛谷P2016

check评论:0 条 remove_red_eye浏览量:371 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-06-30

qwq巨简单的树形dp

#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
struct edge
{
    int next,to;
}e[1500<<1];
int ans=0x3f3f3f3f;
int n;
int tot=0;
int head[2000];
int fa[2000];
void add(int u,int v)
{
    tot++;
    e[tot].to=v;
    e[tot].next=head[u];
    head[u]=tot;        
}
int f[2000][3],siz[2000];
void dfs(int u)
{
    siz[u]=1;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa[u])
        {
            continue;
        }
        fa[v]=u;
        dfs(v);
        siz[u]+=siz[v];
    }
}
void dp(int u)
{
    f[u][1]=1;
    f[u][0]=0;
    if(siz[u]==1)
    {
        return ;
    }
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa[u])
        {
            continue;
        }
        dp(v);
        f[u][1]+=min(f[v][0],f[v][1]);
        f[u][0]+=f[v][1];
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        for(int j=1;j<=y;j++)
        {
            int q;
            scanf("%d",&q);
            add(x,q);
            add(q,x);
        }
    }    
    for(int i=0;i<n;i++)
    {
        fa[i]=i;
        dfs(i);
        dp(i);
        ans=min(ans,min(f[i][1],f[i][0]));
    }
    cout<<ans;
    return 0;
}

chevron_left 洛谷P1816 忠诚
代码风格有关 chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名