Cell Phone Network

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的全部内容，希望文章能够帮你解决所遇到的问题。

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