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
错误原因:
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; }
void dfs(int i, int fa) { 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; }
by loris @ 2021-07-09 14:12:20
谢谢!Orz 好像来的太晚了