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(树的最小点覆盖)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。