POJ3659 Cell Phone Network

POJ3659 Cell Phone Network
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 3782
Accepted: 1305
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
*********************************************************************
제목 대의: 나무 한 그루를 정하고 최소 지배집을 구한다.가장 적은 점으로 이 나무의 모든 가장자리를 덮는다는 것이다.
문제 풀이 사고방식: 제 생각이 좀 이상하고 여러분의 일반적인 사고방식과 많이 다르다는 것을 발견했습니다.나는 각 점에 세 가지 상태를 설정했다. 0은 이 점이 덮어씌워지지 않았다는 것을 나타내고 아버지 노드에 덮어씌워지기를 기대하고 있다. 1은 현재 노드가 지배집에 속한다는 것을 나타내고 2는 현재 노드가 그의 아들에게 덮어씌워진다는 것을 나타낸다.
상태 이동: dp[root][0]=sum{dp[son][2]};
　　　　　　dp[root][1]=sum{min{dp[son][0],dp[son][1],dp[son][2]}};
　　　　　　dp[root][2]=sum{min{dp[son][1],dp[son][2]}};이것은 비교적 특수하다. 괄호 안에서 작아질 때 만약에 계속 dp[son][2]를 취하면 특수 처리가 필요하다. 즉, 반드시 dp[son][1]의 값을 취해야 한다는 것이다.그리고 이 방법의 경계 처리는 비교적 번거롭다.

#include <stdio.h>

#include <vector>

#include <string.h>

#define N 10005

#define INF 2000000

#define MIN(a,b) ((a)<(b)?(a):(b))

using namespace std;



vector<int>gra[N];

int fa[N],dp[N][3],n;



void dfs(int s,int f)

{

    fa[s]=f;

    dp[s][0]=0;

    dp[s][1]=1;

    dp[s][2]=0;

    if(gra[s].size()==1&&gra[s][0]==f)

    {

        dp[s][2]=INF;

        return ;

    }

    int mark=0;

    for(int i=0;i<gra[s].size();i++)

    {

        int t=gra[s][i];

        if(t==f)continue;

        dfs(t,s);

        dp[s][1]+=MIN(MIN(dp[t][0],dp[t][1]),dp[t][2]);

        dp[s][0]+=dp[t][2];

        if(dp[t][1]<=dp[t][2])

        {

            mark=1;

            dp[s][2]+=dp[t][1];

        }

        else

            dp[s][2]+=dp[t][2];

    }

    if(mark)return ;

    int temp=INF;

    for(int i=0;i<gra[s].size();i++)

    {

        int t=gra[s][i];

        if(t==f)continue;

        temp=MIN(temp,dp[s][2]+dp[t][1]-dp[t][2]);

    }

    if(temp!=INF)

        dp[s][2]=temp;

}



void re(void)

{

    scanf("%d",&n);

    memset(fa,0,sizeof(fa));

    memset(dp,0,sizeof(dp));

    for(int i=1;i<=n;i++)

        gra[i].clear();

    for(int i=1;i<n;i++)

    {

        int a,b;

        scanf("%d%d",&a,&b);

        gra[a].push_back(b);

        gra[b].push_back(a);

    }

}



void run(void)

{

    dfs(1,-1);

    printf("%d
",MIN(dp[1][1],dp[1][2]));

}



int main()

{

    re();

    run();

}