POJ 3659——Cell Phone Network

Cell Phone Network

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 4416	Accepted: 1562

Description

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.

Input

* 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

Output

* Line 1: A single integer indicating the minimum number of towers to install

Sample Input

5
1 3
5 2
4 3
3 5
      

Sample Output

2
      

Source

USACO 2008 January Gold

/*算法思想：
  給一棵樹，選擇最少的頂點使得整棵樹被覆寫
  樹形dp
  由于每個節點被覆寫的方式隻有兩種：被相鄰節點覆寫和自己覆寫自己，那麼，我們可以給每個節點三個狀态：
  f[i][0]：表示節點 i 被它的父親覆寫，以 i 為根的子樹需要覆寫的頂點的最少數量
  f[i][1]：表示節點 i 自己覆寫自己，以 i 為根的子樹需要覆寫的頂點的最少數量
  f[i][2]：表示節點 i 被它的兒子覆寫，以 i 為根的子樹需要覆寫的頂點的最少數量
  那麼就有一下狀态轉移方程：
  1、f[i][0]+=min(f[i_son][1] , f[i_son][2])
  2、f[i][1]+=min(f[i_son][0] , f[i_son][1] , f[i_son][2]) +1
  3、f[i][2]+=min(f[i_son][1] , f[i_son][2])
  對于第三個狀态轉移方程：當所有的 f[i_son][2]<f[i_son][1] 時，第 i 個節點實際上是沒有被它的兒子覆寫
  的。是以，我們要找一個兒子，用它來覆寫 i 節點；這種情況下，我們需要增加 f[i][2] 的值。增加的值就是
  找 f[i_son][1]-f[i_son][2] 那麼，用來覆寫節點 i 的這個兒子應該滿足：f[i_son][1]-f[i_son][2] 最小。
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 0x7fffffff
using namespace std;
struct data
{
    int st,en,next;
} edge[20005];
int f[20005][3],d[20005];
int head[20005],tot;
void add_edge(int st,int en)  //加邊
{
    edge[tot].st=st;
    edge[tot].en=en;
    edge[tot].next=head[st];
    head[st]=tot++;
}
void dfs(int u,int fa)  //dfs過程
{
    if(d[u]==1 && u!=1)  //葉子節點
    {
        f[u][0]=0;
        f[u][1]=1;
        f[u][2]=INF;
        return;
    }
    bool fg=true;
    int Min=INF;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        if(edge[i].en==fa) continue;  //樹，排除重邊
        dfs(edge[i].en,u);
        f[u][0]+=min(f[edge[i].en][1],f[edge[i].en][2]);
        f[u][1]+=min(min(f[edge[i].en][0],f[edge[i].en][1]),f[edge[i].en][2]);
        if(f[edge[i].en][1]<=f[edge[i].en][2])
        {
            f[u][2]+=f[edge[i].en][1];
            fg=false;
        }
        else
        {
            f[u][2]+=f[edge[i].en][2];
            Min=min(f[edge[i].en][1]-f[edge[i].en][2],Min);  //找最小的需要添加的值
        }
    }
    f[u][1]++;
    if(fg) f[u][2]+=Min;
}
int main()
{
    int n,a,b;
    while(scanf("%d",&n)!=EOF)
    {
        memset(head,-1,sizeof(head));
        tot=0;
        memset(d,0,sizeof(d));
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            add_edge(a,b);
            add_edge(b,a);
            d[a]++;
            d[b]++;
        }
        memset(f,0,sizeof(f));
        dfs(1,0);
        if(n!=1) printf("%d\n",min(f[1][1],f[1][2]));
        else printf("1\n");
    }
    return 0;
}