Strategic game(树的最小点覆盖)

Strategic game

题意：

一个树，在一个节点放兵，周围的边就被守护，守护所有的边，问最少放多少兵

题解：

这种问题又称树的最小点覆盖
dp[x][1]以x为根的子树全被看住且在x上放置士兵的最少所需的士兵数量
dp[x][0]以x为根的子树全被看住且在x上没有 放置士兵的最少所需的士兵数量.
确定状态方程：
dp[x][1]=1+∑min(dp[i][0],dp[i][1])//x上放了士兵，x的儿子们可放可不放
dp[x][0]=∑dp[i][1]//如果x不放士兵，x的儿子必须放
结果min(dp[root][0],dp[root][1])
i是x的儿子
相当于我们在考虑x点时，x的子节点都是被考虑完的，x能否被覆盖完全取决于自身或x的儿子

代码：

#include<bits/stdc++.h> #define debug(a,b) printf("%s = %d\n",a,b) typedef long long ll; using namespace std;inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=2e3+9; int dp[maxn][3]; vector<int>vec[maxn]; void dfs(int root,int fa) {dp[root][1]=1;dp[root][0]=0;for(int i=0;i<vec[root].size();i++){int v=vec[root][i];if(v==fa)continue;dfs(v,root);dp[root][0]+=dp[v][1];dp[root][1]+=min(dp[v][0],dp[v][1]);} } int main() {int n;while(cin>>n){for(int i=0;i<=maxn;i++)vec[i].clear();memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++){int x,y;scanf("%d:(%d)",&x,&y);for(int j=1;j<=y;j++){int op;cin>>op;vec[x].push_back(op);vec[op].push_back(x);}}dfs(0,-1);printf("%d\n",min(dp[0][0],dp[0][1]));}return 0; }

总结

以上是生活随笔为你收集整理的Strategic game(树的最小点覆盖)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。