蒟蒻求助!QAQ

P2016 战略游戏

diu· @ 2019-10-28 19:01:45

哪儿错了呀,搞不懂呀 QWQ

而且编号从0开始work函数里面就是无限循环 编号从1开始就可以过样例,蒟蒻要 哭了

代码:

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define N 1550
#define Bor(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
struct Node{int num,c[N];}dis[N];
inline int _read();
inline void input();
int n,rt=1,vis[N],dp[N][5];

inline void work(int x)
{
    dp[x][1]=1,dp[x][0]=0;
    if(!dis[x].num) return;
    Bor(i,1,dis[x].num)
    {

        int v=dis[x].c[i];
        work(v);
        dp[x][0]+=dp[v][1];
        dp[x][1]+=min(dp[v][0],dp[v][1]);
    }
}

int main()
{
    input();
    work(rt);
    printf("%d\n",min(dp[rt][1],dp[rt][0]));
    return 0;
}
inline void input()
{
    n=_read();
    Bor(i,1,n)
    {
        int a=_read()+1,b=_read();
        dis[a].num=b;
        Bor(j,1,b)
        {
            int x=_read()+1;
            dis[b].c[j]=x;
            vis[x]=1;
        }
    }
    while(vis[rt])rt++;
}

inline int _read()
{
    int sum=0,flag=1;
    char ch=getchar();
    while(ch < '0'||ch > '9')
    {
        if(ch=='-')
        {
            flag=-1;
            ch=getchar();
            break;
        }
        ch=getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        sum=(sum<<3)+(sum<<1)+ch-'0';
        ch=getchar();
    }
    return sum*flag;
}

by Inkyo @ 2019-10-28 19:03:45

%%%


by Inkyo @ 2019-10-28 19:06:42

感觉你的写法好奇妙啊,和我的完全不一样


by diu· @ 2019-10-28 19:06:48

@Inkyo墨攸 快帮我看下,WA完了


by diu· @ 2019-10-28 19:07:13

@Inkyo墨攸 就是找到根节点开始dp


by diu· @ 2019-10-28 19:07:41

@Inkyo墨攸 只有选和不选两种情况,最后取一个min值


by Inkyo @ 2019-10-28 19:09:04

你说的这些我知道啊...可是我看不懂你的代码...


by diu· @ 2019-10-28 19:09:29

@Inkyo墨攸 emmm,哪儿不懂,我给你解释


by Inkyo @ 2019-10-28 19:09:39

对于写了一个链式前向星存图的我真的搞不懂邻接表啊qaq


by diu· @ 2019-10-28 19:10:13

@Inkyo墨攸 至今我还是觉得这个代码 有错


by Inkyo @ 2019-10-28 19:10:29

而且这题不用找root吧,随便选一个作根就行了啊...


| 下一页