[Usaco2008 Jan]电话网络

题目描述

Farmer John决定为他的所有奶牛都配备手机，以此鼓励她们互相交流。不过，为此FJ必须在奶牛们居住的N(1 <= N <= 10,000)块草地中选一些建上无线电通讯塔，来保证任意两块草地间都存在手机信号。所有的N块草地按1..N 顺次编号。 所有草地中只有N-1对是相邻的，不过对任意两块草地A和B(1 <= A <= N; 1 <= B <= N; A != B)，都可以找到一个以A开头以B结尾的草地序列，并且序列中相邻的编号所代表的草地相邻。无线电通讯塔只能建在草地上，一座塔的服务范围为它所在的那块草地，以及与那块草地相邻的所有草地。 请你帮FJ计算一下，为了建立能覆盖到所有草地的通信系统，他最少要建多少座无线电通讯塔。

输入格式

第1行: 1个整数，N

第2..N行: 每行为2个用空格隔开的整数A、B，为两块相邻草地的编号

输出格式

第1行: 输出1个整数，即FJ最少建立无线电通讯塔的数目

在树上求最小值可以用树形动规。

如果当前点u的父亲pre建了塔，那么u的儿子不建塔也可以；或者u的儿子v建了塔，pre不建也可以。所以我们要设计三种状态：

dp(u,0)表示在u建塔的最小值，dp(u,1)表示在pre建塔的最小值，dp(u,2)表示在v建塔的最小值。那么我们列出状态转移方程：

\[ dp[u][0]=\sum_{v{\in}son(u)}Min{\{}dp[v][0],dp[v][1],dp[v][2]{\}};\dp[u][1]=\sum_{v{\in}son(u)}Min(dp[v][0],dp[v][2]); \]

最后我们来推第三个状态的方程：

首先我们在v建了塔之后u的其它儿子就没有必要一定建塔了，我们得到其他儿子不一定建塔的最小值：

\[ \sum_{w{\in}son(u),w!=v}Min(dp[w][0],dp[w][2])=dp[u][1]-Min(dp[v][0],dp[v][2]) \]

那么我们就可以写出最后一个状态的方程：

\[ dp[u][2]=Min_{v{\in}son(u)}{\{}dp[u][1]-Min(dp[v][0],dp[v][2])+dp[v][0]{\}} \]

初始化dp(u,0)=1,dp(u,2)=INF。

时间复杂度为O(N)。

#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 10001
using namespace std;
 
struct edge{
    int to,next;
    edge(){}
    edge(const int &_to,const int &_next){ to=_to,next=_next; }
}e[maxn<<1];
int head[maxn],k;
int dp[maxn][3],n;
 
inline int read(){
    register int x(0),f(1); register char c(getchar());
    while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }
    while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
inline void add(const int &u,const int &v){ e[k]=edge(v,head[u]),head[u]=k++; }
 
void dfs(int u,int pre){
    dp[u][0]=1,dp[u][2]=0x3f3f3f3f;
    for(register int i=head[u];~i;i=e[i].next){
        int v=e[i].to;
        if(v==pre) continue;
        dfs(v,u);
        dp[u][0]+=min(dp[v][0],min(dp[v][1],dp[v][2]));
        dp[u][1]+=min(dp[v][0],dp[v][2]);
    }
    for(register int i=head[u];~i;i=e[i].next){
        int v=e[i].to;
        if(v!=pre) dp[u][2]=min(dp[u][2],dp[u][1]-min(dp[v][0],dp[v][2])+dp[v][0]);
    }
}
 
int main(){
    memset(head,-1,sizeof head);
    n=read();
    for(register int i=1;i<n;i++){
        int u=read(),v=read();
        add(u,v),add(v,u);
    }
    dfs(1,1);
    printf("%d\n",min(dp[1][0],dp[1][2]));//1没有父亲所以不存在dp[1][1]
    return 0;
}

[Usaco2008 Jan]电话网络

原文：https://www.cnblogs.com/akura/p/10986852.html