当前位置：首页 > article >正文

树型DP # 战略游戏

article 2025/1/5 11:06:40

文章目录

原题链接
题目解读
完整代码
参考

原题链接

题目解读

在这里插入图片描述

f[u][0] 表示 u点上不放士兵的最小花费

f[u][1] 表示 u点上放士兵的最小花费

如果u点不放士兵，那么其子节点必须放士兵，不然这两条边不能同时被瞭望

如果u点放士兵，那么其子节点可放可不放，取min计算即可

完整代码

//这里是引入了一些常用的头文件,和一些常规操作
//第一行是因为该死的编译器不让直接用scanf
#define _CRT_SECURE_NO_WARNINGS 1
#define _USE_MATH_DEFINES //启用M_PI的定义
#include<algorithm>
#include<iostream>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#define MAX 0x3f3f3f3f
#define MIN -0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int N = 1510;
int e[N], ne[N], h[N],idx;
int n, f[N][2];
bool st[N];

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u, int fa) {
	f[u][0] = 0;
	f[u][1] = 1;

	for (int i = h[u]; ~i; i = ne[i]) {
		int j = e[i];
		if (j == fa)continue;
		dfs(j, u);
		f[u][0] += f[j][1];
		f[u][1] += min(f[j][0],f[j][1]);
	}
}

int main() {
	memset(h, -1, sizeof h);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		int id, cnt;
		cin >> id >> cnt;
		while (cnt--) {
			int ver;
			cin >> ver;
			add(id, ver);
			st[ver] = true;
		}
	}

	int root = 0;
	while (st[root])root++;

	dfs(root,-1);

	cout << min(f[root][0], f[root][1]);

	return 0;
}