[USACO 2008 Jan G]Cell Phone Network

本文主要是介绍[USACO 2008 Jan G]Cell Phone Network，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

链接：https://ac.nowcoder.com/acm/problem/24953
来源：牛客网

Farmer John has decided to give each of his cows a cell phone in hopes to encourage their social interaction. This, however, requires him to set up cell phone towers on his N (1 ≤ N ≤ 10,000) pastures (conveniently numbered 1…N) so they can all communicate.
Exactly N-1 pairs of pastures are adjacent, and for any two pastures A and B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B) there is a sequence of adjacent pastures such that A is the first pasture in the sequence and B is the last. Farmer John can only place cell phone towers in the pastures, and each tower has enough range to provide service to the pasture it is on and all pastures adjacent to the pasture with the cell tower.
Help him determine the minimum number of towers he must install to provide cell phone service to each pasture.
输入描述:

• Line 1: A single integer: N
• Lines 2…N: Each line specifies a pair of adjacent pastures with two space-separated integers: A and B
  输出描述:
• Line 1: A single integer indicating the minimum number of towers to install
  示例1
  输入
  复制
  5
  1 3
  5 2
  4 3
  3 5
  输出
  复制
  2
  说明
  The towers can be placed at pastures 2 and 3 or pastures 3 and 5.

一道非常经典的树形DP

大意是在一个树上选取一些点使得这棵树能够被全部覆盖，即一个点可以覆盖所有与之相连的边，此又称为最小支配集
我更习惯叫他状态机模型，因为不同的状态存在不同的转化关系；

考虑动态规划时
f[i][0] 选择i的最少覆盖方案
f[i][1] 选择i的儿子的最少覆盖方案
f[i][2] 选择i的父亲的最少覆盖方案

f[i][0]+=min{f[son][0],f[son][1],f[son][2]};
f[i][2]+=min(f[son][1],f[son][2])
f[i][1]的则较为复杂，因为f[i][1]成立的前提是其儿子中至少有一个选取f[i][0]，即选取自身，因此要做如下讨论
如果u无子节点 f[i][1]=INF
否则 f[i][1]+=min(f[i][0],f[i][1])+inc. ;
其中inc.表示一个变化项，inc=0 if exits f[i][0] < f[i][1] else inc=min{f[i][0]-f[i][1]}
(没有f[son][0]小于f[son][1]的就选二者差最小的)

#include<bits/stdc++.h>
using namespace std;
#define N 10010

int n;
int e[N*2],ne[N*2],h[N],idx=0;
int f[N][3];

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u,int pre){
    f[u][0]=1,f[u][1] = f[u][2] = 0;
    bool flag=true;
    int tmp=0x3f3f3f3f;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==pre) continue;
        dfs(j,u);
        f[u][2]+=min(f[j][1],f[j][0]);
        f[u][0]+=min(min(f[j][0],f[j][1]),f[j][2]);
        if(f[j][0]<=f[j][1]){
            flag=false;
            f[u][1]+=f[j][0];
        }
        else{
            f[u][1]+=f[j][1];
            tmp=min(tmp,f[j][0]-f[j][1]);
        }
    }
    if(flag) f[u][1]+=tmp;
}

int main(){
    memset(f,0x3f,sizeof f);
    memset(h,-1,sizeof h);
    
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }
    
    dfs(1,-1);
    
    int ans=min(f[1][0],f[1][1]);
    
    cout << ans << endl;
    
    return 0;
}

这篇关于[USACO 2008 Jan G]Cell Phone Network的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！