洛谷2016 战略游戏

access_time    bookmark 题解    comment 0 条评论    提高+/省选-

重题,双倍经验。

https://llf0703.com/p/uva-1292.html

而且uva的题还有多组输出,删掉就行了。

struct Edge{
    int next,to;
} edge[3005];
int head[1505],n,m,a,b,c,cnt,f[1505][2],out[1505];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x)
{
    f[x][1]=1;
    f[x][0]=0;
    if (!head[x]) return;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        dfs(y);
        f[x][0]+=f[y][1];
        f[x][1]+=min(f[y][1],f[y][0]);
    }
    return;
}

int main()
{
    n=read();
    for (int i=1;i<=n;i++)
    {
        a=read(); b=read();
        a++;
        for (int j=1;j<=b;j++)
        {
            c=read();
            c++;
            add(a,c);
            out[c]++;
        }
    }
    int i=1;
    while (out[i]) i++;
    dfs(i);
    printf("%d\n",min(f[i][0],f[i][1]));
    return 0;
}

新评论

account_circle
称呼不能为空
email
邮箱格式不合法
link
网站格式不合法
textsms
内容不能为空

第一次提交或含有敏感词汇的评论将在审核后显示。