hust 1036 Cell Phone Network

浏览数：18 / 时间：2015年06月09日

题目描述

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

样例输入

样例输出

2
这道题其实网上有很多题解，还将的很好，就是简单的树形dp，一个节点可以放，也可以不放，而不放的时候分两种情况，1，它不放，但是它的某个儿子放了，2，它不放，但是它的父亲放了
在球它不放，它的儿子放的时候注意，不要一味的取最小值，还要判断选的是不是都是它的儿子不放，儿子的父亲放的情况

#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define  inf 0x0f0f0f0f
 
using namespace std;
 
//const int inf=100000000;
 
const double pi=acos(-1.0);
const double eps=1e-8;
typedef pair<int,int>pii;
 
const int maxn=10001;
 
vector<int>mmap[maxn];
int dp[maxn][3];
 
void dfs(int son , int fa)
{
    dp[son][0]=0;
    dp[son][1]=0;
    dp[son][2]=1;
    if (mmap[son].size()==1 && mmap[son][0]==fa )
    {
        dp[son][1]=inf;
        return;
    }
    int minx=inf,temp=0,flag=0;
    for (int i=0;i<mmap[son].size();i++)
    {
        int v=mmap[son][i];
        if (v!=fa){
            dfs(mmap[son][i],son);
            dp[son][0]+=min(dp[v][1],dp[v][2]);
            dp[son][2]+=min(dp[v][0],min(dp[v][1],dp[v][2]));
            if (dp[v][1]<dp[v][2])
            {
                dp[son][1]+=dp[v][1];
                if (minx>dp[v][2])
                {
                    minx=dp[v][2];
                    temp=dp[v][1];
                }
            }
            else
            {
                flag=1;
                dp[son][1]+=dp[v][2];
            }
        }
    }
    if (!flag)
        dp[son][1]+=minx-temp;
}
 
int main()
{
    //freopen("in.txt","r",stdin);
 
    int n,x,y;
    while (scanf("%d",&n)!=EOF)
    {
        for (int i=0;i<=n;i++) mmap[i].clear();
        for (int i=1;i<n;i++)
        {
            scanf("%d%d",&x,&y);
            mmap[x].push_back(y);
            mmap[y].push_back(x);
        }
        //memset(dp,0,sizeof(dp));
        dfs(1,-1);
        printf("%d\n",min(dp[1][1],dp[1][2]));
    }
    //fclose(stdin);
    return 0;
}