给定一棵n个结点的树,至少要选多少个点才能覆盖所有边?边的两个端点至少有一个被选中则认为覆盖。
1<=n<=1500
分析:设dp[i][0]表示以i为根的子树,不选i的答案,同理dp[i][1]为选i的答案。自下而上dp,如果选了i,那么其子节点可以选或不选;如果不选i,那么其子节点必须选。
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int n;
std::cin >> n;
std::vector<std::vector<int>> adj(n);
for (int i = 0; i < n; i++) {
int x, y;
std::cin >> x >> y;
for (int j = 0; j < y; j++) {
int z;
std::cin >> z;
adj[x].push_back(z);
adj[z].push_back(x);
}
}
std::vector<std::array<int,2>> dp(n);
auto dfs = [&](auto self, int x, int p) -> void {
dp[x][0] = 0;
dp[x][1] = 1;
for (auto i : adj[x]) if (i != p) {
self(self, i, x);
dp[x][0] += dp[i][1];
dp[x][1] += std::min(dp[i][0], dp[i][1]);
}
};
dfs(dfs, 0, 0);
std::cout << std::min(dp[0][0], dp[0][1]) << "\n";
}
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int t = 1;
while (t--) solve();
return 0;
}
标签:std,luoguP2016,游戏,int,self,dfs,战略,adj,dp
From: https://www.cnblogs.com/chenfy27/p/18523491