树形DP入门题萌新求助
  • 板块P2016 战略游戏
  • 楼主qip101
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/8/9 15:25
  • 上次更新2023/10/27 16:17:29
查看原帖
树形DP入门题萌新求助
333800
qip101楼主2022/8/9 15:25
#include <iostream>
#include <cstdio>
#include <cstdlib> 
#include <algorithm>
#include <vector>
#define MAXN 5050
using namespace std;
int n,f[MAXN][5];
vector <int> G[MAXN];
inline void dfs(int u,int fa)
{
	f[u][0]=0;f[u][1]=1;
	for(register int i=1;i<G[u].size();i++)
	{
		int v=G[u][i];
		if(v==fa) 
			continue;
		dfs(v,u);
		f[u][0]+=f[v][1];
		f[u][1]+=min(f[u][1],f[u][0]);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n;
	while(n--)
	{
		int u,k;
		cin >> u >> k;
		for(register int i=1;i<=k;i++)
		{
			int v;
			cin >> v;
			G[u].push_back(v);
		}
	}
	dfs(0,-1);
	cout << min(f[0][0],f[0][1]) << endl;
	return 0;
}
2022/8/9 15:25
加载中...