文章目录
- 原题链接
- 题目解读
- 完整代码
- 参考
原题链接
题目解读
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;
}参考
本篇文章参考于 ACWING算法平台
董晓算法
感谢🌹
🌻编写本篇文章目的是笔者想以输出的形式进行学习，顺便记录学习点滴🌻
🌹 如果本篇文章对你有帮助的话那就点个赞吧👍🌹
😇 本篇文章可能存在多处不足，如有修改意见，可以私信或者评论我哦 😇
