poj 3659 (树上的最小支配集)

贪心，先用dfs从1号结点开始，将经过的每个点都记录下来，然后反向贪心，这样就可以保证每次都先判断完子结点然后再判断父结点。然后就是在在判断每两个相邻的点时（必须取一个），我们为了保证选的点数最小所以每次都选这个点的父亲结点，因为选了父亲结点绝对比选这个结点优。然后每次都这样选择那么就可以保证最后结果最优。然后要注意的是，每次确定一个点为支配集后，这个点的父亲结点也标记为可以到达的.

Cell Phone Network

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 4930		Accepted: 1739

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

Sample Output

Source

USACO 2008 January Gold

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
#define N 10010

struct node
{
    int to,next;
}edge[2*N];

int cnt,pre[N];
int p[N];
int g[N];
int num;
int mark[N];

void add_edge(int u,int v)
{
    edge[cnt].to=v;
    edge[cnt].next=pre[u];
    pre[u]=cnt++;
}

void DFS(int s)
{
    g[num++]=s;
    mark[s]=1;
    for(int p1=pre[s];p1!=-1;p1=edge[p1].next)
    {
        int v=edge[p1].to;
        if(mark[v]==0)
        {
            p[v]=s;
            DFS(v);
        }
    }
}

int greedy()
{
    int set[N];
    memset(mark,0,sizeof(mark));
    memset(set,0,sizeof(set));
    int sum=0;
    for(int i=num-1;i>=0;i--)
    {
        int k=g[i];
        if(mark[k]==0)    
        {
            if(set[p[k]]==0)
            {
                set[p[k]]=1;
                sum++;
            }
            mark[k]=1;
            mark[p[k]]=1;
            mark[p[p[k]]]=1;
        }
    }
    return sum;
}

int main()
{
    int n;
    scanf("%d",&n);
    cnt=0;
    num=0;
    memset(pre,-1,sizeof(pre));
    memset(mark,0,sizeof(mark));
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add_edge(x,y);
        add_edge(y,x);
    }
    p[1]=1;
    DFS(1);
    printf("%d",greedy());
    return 0;
}