poj-3659 Cell Phone Network（最小支配集+贪心）-程序员宅基地

http://poj.org/problem?id=3659

 

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

题目大意：

John想让他的所有牛用上手机以便相互交流(也是醉了。。。)，他需要建立几座信号塔在N块草地中。已知与信号塔相邻的草地能收到信号。给你N-1个草地(A，B)的相邻关系

问：最少需要建多少个信号塔能实现所有草地都有信号。

 

思路：考察树最小支配集问题。可以学习学习别人的博客https://www.cnblogs.com/i-love-acm/p/3558238.html

 

最小支配集：从所有顶点中取尽量少的点组成一个集合，使得剩下的所有点都与取出来的点有边相连。顶点个数最小的支配集被称为最小支配集。

这里用贪心法来求:

1.以1号点深度优先搜索整棵树，求出每个点在DFS中的编号和每个点的父亲节点编号。

2.按DFS的反向序列检查，如果当前点既不属于支配集也不与支配集中的点相连，且它的父亲也不属于支配集，将其父亲点加入支配集，支配集个数加1。

3.标记当前结点、当前结点的父节点(属于支配集)、当前结点的父节点的父节点(与支配集中的点相连)。

 

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
const int INF=0x3f3f3f3f;
using namespace std;

int n;
int Index;
int cnt_edge;
int node[10010];
int fa[10010];
int vis[10010];
int DFN[10010];
int F[10010];

struct Edge{
    int to;
    int next;
}E[20010];

void add_edge(int a,int b)
{
    E[cnt_edge].next=node[a];
    E[cnt_edge].to=b;
    node[a]=cnt_edge++;
}

void DFS(int u)
{
    DFN[Index++]=u;
    for(int i=node[u];i!=-1;i=E[i].next)
    {
        int v=E[i].to;
        if(!vis[v])
        {
            fa[v]=u;
            vis[v]=1;
            DFS(v);
        }
    }
}

int solve()
{
    int ans=0;
    memset(vis,0,sizeof(vis));
    for(int i=Index-1;i>=0;i--)
    {
        int v=DFN[i];
        if(!vis[v])
        {
            if(!F[fa[v]])
            {
                F[fa[v]]=1;
                ans++;
            }
            vis[v]=1;
            vis[fa[v]]=1;
            vis[fa[fa[v]]]=1;
        }
    }
    return ans;
}

int main()
{
    scanf("%d",&n);
    memset(node,-1,sizeof(node));
    for(int i=1;i<n;i++)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        add_edge(a,b);
        add_edge(b,a);
    }
    vis[1]=1;
    DFS(1);
    printf("%d\n",solve());
    return 0;
}