hdu-1054-Strategic Game
  VrZI4Uwu8BR1 2023年11月02日 80 0


#include<cstdio>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<iomanip>
using namespace std;

int dp[1550][2];
vector<int> f[1550];
int p[1550];

void dfs(int v)
{
    if(f[v].size()==0)
    {
        dp[v][0]=0;
        dp[v][1]=1;
    }
    else
    {
        int i;
        for(i=0;i<f[v].size();i++)
        {
            int u=f[v][i];
            dfs(u);
            dp[v][0]+=dp[u][1];
            dp[v][1]+=min(dp[u][0],dp[u][1]);
        }
        dp[v][1]++;
    }
}
int main()
{
    int i,j;
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int nn=n;
        memset(p,0,sizeof(p));
        memset(dp,0,sizeof(dp));
        for(i=0;i<=n;i++)
            f[i].clear();
        while(n--)
        {
            int t1,m;
            scanf("%d:(%d)",&t1,&m);
            while(m--)
            {
                int t2;
                cin>>t2;
                f[t1].push_back(t2);
                p[t2]=1;
            }
        }
        int k;
        for(i=0;i<nn;i++)
            if(p[i]==0)
            {
                k=i;
                break;
            }
        dfs(k);
        printf("%d\n",min(dp[k][0],dp[k][1]));
    }
    
    //system("pause");
}



【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 2023年11月08日 0

暂无评论

推荐阅读
VrZI4Uwu8BR1