Cell Phone Network

題意:

每個牧場的電塔可以覆蓋與該牧場相鄰的電塔，為了讓所有牛都可以打電話，求建的電塔的最小數量

題解：

樹的最小支配集
dp[x][0]：選點i，并且以點i為根的子樹都被覆蓋
dp[x][1]：不選i，i被其兒子覆蓋
dp[x][2]：不選點i，i被其父親覆蓋（此時兒子可選可不選）
轉移方程：
dp[i][0]=1+∑min(dp[u][0],dp[u][1],dp[u][2])(u是i的兒子)
被兒子被自己被父親覆蓋

dp[i][2]=∑(dp[u][1],dp[u][0])
i被父親覆蓋，u是i的兒子，u 可選可不選，但是u肯定不會被i所覆蓋

對于dp[i][1]情況，i的兒子們中必須有一個取dp[u][0]
if(i沒有子節點)dp[i][1]=INF
else dp[i][1]=∑min（dp[u][0],dp[u][1]）+inc
對于inc
if(∑min（dp[u][0],dp[u][1]）中包含某個dp[u][0])inc=0
else inc=min(dp[u][0]-dp[u][1])
選與不選
若dp[u][0]>dp[u][1]，即所有子節點都不染色，所以我們必須強迫一個子節點染色且保證最優解dp[root][1]+=min;

代碼:

#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=1e4+9; const int INF=1e9+9; vector<int>vec[maxn]; /* dp[u][0]表示節點u建站點最少數目 dp[u][1]表示節點u的子節點有建，u不建 dp[u][2]表示節點u能夠被父親節點覆蓋，u不建 */ int vis[maxn]; int dp[maxn][5]; void dfs(int u) {dp[u][0]=1;dp[u][1]=dp[u][2]=0;vis[u]=1;int Min=INF;bool f=1;for(int i=0;i<vec[u].size();i++){int v=vec[u][i];if(vis[v])continue;dfs(v);dp[u][0]+=min(dp[v][0],min(dp[v][1],dp[v][2]));dp[u][2]+=min(dp[v][0],dp[v][1]);if(dp[v][0]<=dp[v][1]){f=0;dp[u][1]+=dp[v][0];}else {dp[u][1]+=dp[v][1];Min=min(dp[v][0]-dp[v][1],Min);}}if(f)dp[u][1]+=Min;} int main() {int n;cin>>n;for(int i=1;i<n;i++){int u,v;cin>>u>>v;vec[u].push_back(v);vec[v].push_back(u);}dfs(1);printf("%d\n",min(dp[1][0],dp[1][1]));return 0; }

總結

以上是生活随笔為你收集整理的Cell Phone Network的全部內容，希望文章能夠幫你解決所遇到的問題。

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