uva 1218——Perfect Service

￡神魔★判官ぃ 2022-08-18 02:40 28阅读 0赞

题意：有n个机器组成的树形结构，要求一台服务器必须连接一台电脑，求使用的最少的服务器。。

思路： 树形DP，和前面的有道题目类似。在dfs遍历树的时候找到选当前结点和不选当前节点的最大状态，多一个两个都不是而儿子是节点的情况。

code：

#include <bits/stdc++.h>
    using namespace std;
    
    #define ft(i,s,t) for (int i=s;i<=t;i++)
    #define frt(i,t,s) for (int i=t;i>=s;i--)
    #define cls(v,c) memset(v,c,sizeof(v))
    const int INF=0x3f3f3f3f;
    const int N=1e5+1e4;
    
    int dp[N][3],n,x,y;
    vector<int>v[N];
    int vis[N];
    
    void dfs(int u)
    {
        vis[u]=1;
        dp[u][0]=1;dp[u][1]=0;dp[u][2]=N;
        int pt=-1,len=v[u].size();
    
        for (int i=0;i<len;i++)
        {
            int t=v[u][i];
            if (!vis[t])
            {
                dfs(t);
                dp[u][0]+=min(dp[t][0],dp[t][1]);
                dp[u][1]+=dp[t][2];
            }else pt=i;
        }
        if (pt>=0) len--,v[u][pt]=v[u][len];
        for (int i=0;i<len;i++)
        {
            int t=v[u][i];
            dp[u][2]=min(dp[u][2],dp[u][1]-dp[t][2]+dp[t][0]);
        }
    }
    int main()
    {
        while (~scanf("%d",&n))
        {
            ft(i,0,n) v[i].clear();cls(vis,0);
            ft(i,1,n-1)
            {
                scanf("%d %d",&x,&y);
                v[x].push_back(y);
                v[y].push_back(x);
            }
            dfs(1);
            printf("%d\n",min(dp[1][0],dp[1][2]));
            scanf("%d",&n);
            if (n==-1) break;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，28人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 1218

网络上有一种是发现打开门的规律，然后用数学的方法来解决的，但是一般发现比较困难。所以用了模拟的方法模拟器过程，用数组代表门的状态。 package test; im

古城微笑少年丶/ 2022年09月29日 06:02/ 0 赞/ 115 阅读

相关 uva 1218——Perfect Service

题意：有n个机器组成的树形结构，要求一台服务器必须连接一台电脑，求使用的最少的服务器。。思路：树形DP，和前面的有道题目类似。在dfs遍历树的时候找到选当前结点

￡神魔★判官ぃ/ 2022年08月18日 02:40/ 0 赞/ 29 阅读

相关 uva 10622——Perfect P-th Powers

题意：给定一个数n，求最大的一个数k使得n=x^k。思路1：正规的做法是把这个素数分解，然后求指数的最大公约数就是所求（听说有人取了最小值也能过，数据水吧！），素数

小灰灰/ 2022年08月09日 13:48/ 0 赞/ 289 阅读

相关 poj1218

include<stdio.h> include<math.h> int main() { int i,n,j,k,

系统管理员/ 2022年06月18日 04:19/ 0 赞/ 207 阅读

相关 367. Valid Perfect Square

/ Given a positive integer num, write a function which returns True if num is a

青旅半醒/ 2022年06月09日 05:38/ 0 赞/ 251 阅读

相关 [1218] You are my brother

\[1218\] You are my brother 时间限制: 1000 ms　内存限制: 131072 K 问题描述 Little A gets

柔情只为你懂/ 2022年02月26日 04:06/ 0 赞/ 246 阅读

相关 (BZOJ1218)激光炸弹

题目链接：[https://www.acwing.com/problem/content/101/][https_www.acwing.com_problem_content_

喜欢ヅ旅行/ 2022年01月22日 09:23/ 0 赞/ 332 阅读

相关 UVA - 1218 Perfect Service (树形dp)

题意：有n台电脑，互相以无根树的方式连接，现要将其中一部分电脑作为服务器，且要求每台电脑必须连接且只能连接一台服务器(不包括作为服务器的电脑)，求最少需要多少台电脑作为服务器

柔光的暖阳◎/ 2021年12月18日 08:05/ 0 赞/ 309 阅读

相关 [UVA-1218] Perfect Service（树的最小支配集）

题目链接：[https://vjudge.net/problem/UVA-1218][https_vjudge.net_problem_UVA-1218] 题目大意：给你一棵

港控/mmm°/ 2021年11月02日 09:48/ 0 赞/ 370 阅读

相关 279. Perfect Squares

本周依旧是做与图论相关的题目，作为对图论知识的巩固。题目：279. Perfect Squares Given a positive integer n, find t

ゝ一纸荒年。/ 2021年10月01日 02:22/ 0 赞/ 326 阅读