首页 > 代码库 > [luoguP2016] 战略游戏(DP)

[luoguP2016] 战略游戏(DP)

传送门

 

f[i][0]表示不选当前节点,当前节点的所有儿子节点都选
f[i][1]表示选当前节点,儿子节点可选可不选

 

#include <cstdio>#include <cstring>#include <iostream>#define N 1501#define min(x, y) ((x) < (y) ? (x) : (y))int n, cnt;int head[N], to[N << 1], next[N << 1], f[N][2];bool vis[N];//f[i][0]表示不选当前节点,当前节点的所有儿子节点都选//f[i][1]表示选当前节点,儿子节点可选可不选 inline int read(){	int x = 0, f = 1;	char ch = getchar();	for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;	for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;	return x * f;}inline void add(int x, int y){	to[cnt] = y;	next[cnt] = head[x];	head[x] = cnt++;}inline void dfs(int u){	int i, v;	f[u][1] = vis[u] = 1;	for(i = head[u]; i ^ -1; i = next[i])	{		v = to[i];		if(!vis[v])		{			dfs(v);			f[u][0] += f[v][1];			f[u][1] += min(f[v][0], f[v][1]);		}	}}int main(){	int i, j, k, x, y;	n = read();	memset(head, -1, sizeof(head));	for(i = 1; i <= n; i++)	{		x = read() + 1;		k = read();		for(j = 1; j <= k; j++)		{			y = read() + 1;			add(x, y);			add(y, x);		}	}	dfs(1);	printf("%d\n", min(f[1][0], f[1][1]));	return 0;}

  

[luoguP2016] 战略游戏(DP)