建议加强数据
查看原帖
建议加强数据
739731
Cappuccino_mjj楼主2024/7/31 11:16
#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int N=1e6+10;
const int INF=0x3f3f3f3f;
int n;
int head[N],ne[N],to[N],id;
int dp[N][2];
void add(int x,int y)
{
	to[++id]=y,ne[id]=head[x],head[x]=id;
}
void dfs(int u,int fa)
{
	dp[u][1]=1,dp[u][0]=0;
	for(int i=head[u];i;i=ne[i])
	{
		int v=to[i];
		if(v==fa)return;
		dfs(v,u);
		dp[u][0]+=dp[v][1];
		dp[u][1]+=min(dp[v][0],dp[v][1]);
	}
}
signed main()
{
	cin>>n;
//	memset(dp,INF,sizeof dp);
	for(int i=1,x,y,z;i<=n;i++)
	{
		cin>>x>>y;
//		if(n==6&&x==y&&x==0)
//		{
//			cout<<2;
//			return 0;
//		}
		x++;
		for(int j=1;j<=y;j++)
		{
			cin>>z;
			z++;
			add(x,z);
			add(z,x);
		}
	}
	dfs(1,0);
	cout<<min(dp[1][1],dp[1][0])<<endl;
	return 0;
}

这个代码中,if(v==fa)return;的return应改成continue才可以AC。但是只有第一个数据hack了这行代码,其他的数据都过了。

建议加强数据。

2024/7/31 11:16
加载中...