60分求助wa了QwQ

P2016 战略游戏

loris @ 2021-06-25 16:14:08

#include<bits/stdc++.h>
using namespace std;
const int MM=3500;
int nxt[MM],head[MM],t[MM],f[MM][2],out[MM],l[MM][2],tot,n,m;
void add(int u,int v)
{
    nxt[++tot]=head[u];
    head[u]=tot;
    t[tot]=v;
}
void dfs(int i,int fa)
{
    if(f[i][0]>=0&&f[i][1]>=0)return ;
    if(out[i]==1&&fa!=n+1)
    {
        f[i][0]=0,f[i][1]=1;
        return ;
    }   
    int a=0,b=0;
    for(int j=head[i];j;j=nxt[j])
    {
        if(t[j]==fa)continue ;
        dfs(t[j],i);
        a+=f[t[j]][1];
        b+=min(f[t[j]][0],f[t[j]][1]);
    }
    f[i][1]=b+1;
    f[i][0]=a;
    return ;
}
int main()
{
    cin>>n;int q;
    for(int i=0;i<=n;i++)
    {
        f[i][0]=f[i][1]=-1;
    }
    for(int i=0;i<=n-1;i++)
    {
        cin>>q>>m;out[i]=m;
        for(int j=1;j<=m;j++)
        {
            cin>>q;
            add(i,q);
        }
    }
    dfs(0,n+1);
    cout<<min(f[0][0],f[0][1]);
    return 0;
} 

by 贺俊洁 @ 2021-06-26 20:18:48

错误原因:


by loris @ 2021-07-09 14:12:20

谢谢!Orz 好像来的太晚了


|