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吧,随便选一个作根就行了啊...