UVA 1218 完美服务 （紫薯系列）（树形dp分类讨论与优化）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了UVA 1218 完美服务 （紫薯系列）（树形dp分类讨论与优化），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1915字，纯文字阅读大概需要3分钟。

内容图文

题意： 给你一个无根树，每个节点如果不是服务器，那么它当且仅当与一个服务器相邻。问你在这个无根树中，最少把多少个节点变为服务器，才能使方案合法。

分析：明显的树形dp，按照之前做紫书题目的经验，我们也是把节点分情况讨论，以便覆盖所有状态。

定义 dp (1,u)为： 当前u是服务器。 dp(0,u) 为u不是服务器，但它的父亲是服务器。dp(2,u)为 ： u不是服务器，且它的父亲也不是服务器.

对于dp(1,u) 来说 当前是服务器，那么每个子节点v可以是服务器，也可以不是服务器，取min即可。

对于dp(0,u):它的父亲已经是服务器了，为了保持u只与一个子节点相邻，那么它的子节点一定不能是服务器。注意，子节点的状态是父亲不是服务器，自己也不是服务器。

所以dp(0,u)=  sum(dp(2,v)) (v是u的子节点).

对于dp(2,u),必须u不是叶子结点，该项才合法。因为dp(2,u)父亲不是，自己不是，那么必须要有一个子节点才是。那么，该选哪个子节点成为服务器呢。

可以预见，选一个子节点成为服务器肯定比多选的要好，所以是dp(2,u)= sum - dp(2,v) + dp(1,v) 。其中sum是各个叶结点的dp(2,v)的和。等等！，这个sum其实就是dp(0,u)嘛，实际上我们先更新dp(1,u) 再更新dp(0,u)，最后更新dp(2,u)不就好了？！

最后由于是无根树，我们随便找一个节点当成根就好，那就1号吧。最后答案是min(dp[1][1],dp[2][1])。为什么不考虑dp[0][1]呢，因为它并不合法，因为1是根，它根本就没有父亲嘛。

最后代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10005;
const int INF=10006;
vector<int> v[maxn];
int dp[3][maxn];
void dfs(int u,int fa){
    dp[1][u]=1;dp[0][u]=0;dp[2][u]=INF;
    for(int i=0;i<v[u].size();i++){
        if(v[u][i]==fa) continue;
        dfs(v[u][i],u);
        dp[1][u]+=min(dp[1][v[u][i]],dp[0][v[u][i]]);
        dp[0][u]+=dp[2][v[u][i]];
    }
    for(int i=0;i<v[u].size();i++){
        if(v[u][i]==fa) continue;
        dp[2][u]=min(dp[0][u]+dp[1][v[u][i]]-dp[2][v[u][i]],dp[2][u]);
    }
    return ;
}
int main(){
    int n;
    while(scanf("%d",&n)==1){
        for(int i=0;i<=n;i++){
            v[i].clear();
        }
        for(int i=0;i<n-1;i++){
            int from,to;
            scanf("%d%d",&from,&to);
            v[from].push_back(to);v[to].push_back(from);
        }
        dfs(1,0);
        int op; cin>>op;
                cout<<min(dp[1][1],dp[2][1])<<endl;
        if(op==-1) break;
    }
return 0;}

 

内容总结

以上是互联网集市为您收集整理的UVA 1218 完美服务 （紫薯系列）（树形dp分类讨论与优化）全部内容，希望文章能够帮你解决UVA 1218 完美服务 （紫薯系列）（树形dp分类讨论与优化）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---