最后一组数据咋过不了
查看原帖
最后一组数据咋过不了
675572
syyyyhy楼主2022/3/31 07:29
//战略游戏
#include <bits/stdc++.h>
using namespace std;


int n;
vector<int> g[1520];
int dp[1520][2];

void dfs(int number,int fa)
{
	dp[number][1]=1;
	dp[number][0]=0;
	for(int to:g[number])
	{
		if(to!=fa)
		{
			dfs(to,number);
			dp[number][1]+=min(dp[to][1],dp[to][0]);
			dp[number][0]+=dp[to][1];
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int u;
		cin>>u;
		int num;
		cin>>num;
		if(num==0) break;
		else
		{
			while(num)
			{
				int v;
				cin>>v;
				g[u].push_back(v);
				g[v].push_back(u);
				num--;
			}
		}
	}
	//随便找个节点遍历 
	dfs(0,-1);
	cout<<min(dp[0][0],dp[0][1]);
 }  
2022/3/31 07:29
加载中...