Cell Phone Network （树形dp，最小点覆盖）

2021-01-14 01:12

阅读：505

标签：题目 pre queue net 最小转移 efi scan long

https://ac.nowcoder.com/acm/problem/24953

题目描述：给出一棵树，选最小的点把所以边覆盖。

思路：

• dp[i][0]：选点i，并且以点i为根的子树都被覆盖了。

• dp[i][1]：不选点i，i被其儿子覆盖

• dp[i][2]：不选点i，i没有被子节点覆盖（被其父亲覆盖）

转移：

• dp[i][0]=1+Σmin(dp[v][0],dp[v][1],dp[v][2]) （v是i的儿子）

• dp[i][2]=Σ(dp[u][1]) //所有不覆盖他的儿子和

• dp[i][1]至少需要一个儿子被选，(不然覆盖不了i)，即至少选一个dp[v][0]。

如果没有选到dp[v][0]，我们就把其中一个dp[v][1]花最小的代价变成dp[v][0]。

cost=min(dp[v][0]-dp[v][1]) (v是i儿子)

代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include#define sd(x) scanf("%d",&x)
#define lsd(x) scanf("%lld",&x)
#define ms(x,y) memset(x,y,sizeof x)
#define fu(i,a,b) for(int i=a;i#define fd(i,a,b) for(int i=a;i>=b;i--)
#define all(a) a.begin(),a.end()
#define lson l,mid,rt#define rson mid+1,r,rtusing namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int maxn=1e5+79;
const int mod=998244353;
const ll INF=0x7f7f7f7f;
const double pi=acos(-1);
ll dp[maxn][3];
vectorint> son[maxn];
int n,k;
void dfs(int u,int fa)
{
    //初始化
    dp[u][0]=1;dp[u][1]=0;dp[u][2]=0;
    ll cost=INF;
    bool find=0;
    for(int v:son[u])
    {
        if(v==fa) continue;
        dfs(v,u);
        //dp:0-选点i
        //1-不选，i被儿子覆盖
        //2-不选，i没有被儿子覆盖
        dp[u][0]+=min(min(dp[v][0],dp[v][1]),dp[v][2]);
        dp[u][2]+=dp[v][1];
        //到1的状态，儿子中至少选一个dp[v][0]
        //找不到就找一个dp[v][1]把他变成dp[v][0]，使变化花费最小
        if(dp[v][0]1])
        {
            find=1;
            dp[u][1]+=dp[v][0];
        }
        else
        {
            dp[u][1]+=dp[v][1];
            cost=min(cost,dp[v][0]-dp[v][1]);
        }
    }
　　 //找不到就花最小的代价使得其中一个变
    if(!find) dp[u][1]+=cost;
}
int main()
{
    sd(n);
    fu(i,1,n-1)
    {
        int u,v,w;sd(u);sd(v);
        son[u].push_back(v);
        son[v].push_back(u);
    }
    dfs(1,0);
    //根节点就是答案，根节点必须被自己或儿子覆盖
    printf("%lld\n",min(dp[1][0],dp[1][1]));
    return 0;
}

Cell Phone Network （树形dp，最小点覆盖）

标签：题目 pre queue net 最小转移 efi scan long

原文地址：https://www.cnblogs.com/studyshare777/p/13472868.html

上一篇：CSS的定位

下一篇：分享一个阿里云轻量级开源前端图编排，流程图js组件——butterfly-dag

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Cell Phone Network （树形dp，最小点覆盖）
文章链接：http://soscw.com/index.php/essay/41548.html

亲，登录后才可以留言！

Cell Phone Network （树形dp，最小点覆盖）

评论

热门文章

推荐文章

最新文章

置顶文章