POJ3659 Cell Phone Network【最小支配集】【贪心】

3 5

2

USACO 2008 January Gold

题目大意：John想让他的所有牛用上手机以便相互交流(也是醉了。。。)，他需要建立

几座信号塔在N块草地中。已知与信号塔相邻的草地能收到信号。给你N-1个草地(A，B)

的相邻关系，问：最少需要建多少个信号塔能实现所有草地都有信号。

思路：考察树最小支配集问题。最小支配集：值从所有顶点中取尽量少的点组成一个集

合，使得剩下的所有点都与取出来的点有边相连。顶点个数最小的支配集被称为最小支

配集。这里用贪心法来求。

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

2.按DFS的反向序列检查，如果当前点既不属于支配集也不与支配集中的点相连，且它

的父亲也不属于支配集，将其父亲点加入支配集，支配集个数加1。

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

中的点相连)。

参考：ACM-ICPC程序设计系列——图论及应用 P66~P69

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 20020;

struct EdgeNode
{
    int to;
    int next;
}Edges[MAXN];
int Head[MAXN],father[MAXN],NewPos[MAXN];
bool vis[MAXN];
//NewPos[]表示深度优先遍历序列的第i个点是哪个点
//now表示当前深度优先遍历序列中已经有多少个点了
//vis[]用来深度优先遍历的判重
//father[]表示点i的父亲节点编号
int N,M,now;
void DFS(int x)
{
    NewPos[now++] = x;
    for(int k = Head[x]; k != -1; k = Edges[k].next)
    {
        if(!vis[Edges[k].to])
        {
            vis[Edges[k].to] = true;
            father[Edges[k].to] = x;
            DFS(Edges[k].to);
        }
    }
}

//S[i]为true，表示第i个点被覆盖了
//Set[i]表示点i属于要求的点集
bool S[MAXN],Set[MAXN];
int Greedy()//贪心求最小支配集
{
    memset(S,0,sizeof(S));
    memset(Set,0,sizeof(Set));
    int ans = 0;
    for(int i = N-1; i >= 1; i--)//反向序列检查
    {
        int t = NewPos[i];
        if(!S[t])//当前点未被覆盖，也就是当前点既不属于支配集，夜不语支配集中的点相连
        {
            if(!Set[father[t]])//当前点的父亲结点不属于支配集，
            {
                Set[father[t]] = true;  //将父节点加入支配集
                ans++;                  //支配集个数加1
            }
            S[t] = true;
            S[father[t]] = true;
            S[father[father[t]]] = true;
            //标记当前点、当前结点的父节点、当前结点的父节点的父节点
        }
    }
    return ans;
}

int main()
{
    int u,v;
    while(~scanf("%d",&N))
    {
        memset(Edges,0,sizeof(Edges));
        memset(Head,-1,sizeof(Head));
        memset(father,0,sizeof(father));
        memset(vis,false,sizeof(vis));
        memset(NewPos,0,sizeof(NewPos));
        int id = 0;
        for(int i = 0; i < N-1; ++i)
        {
            scanf("%d%d",&u,&v);
            Edges[id].to = v;
            Edges[id].next = Head[u];
            Head[u] = id++;
            Edges[id].to = u;
            Edges[id].next = Head[v];
            Head[v] = id++;
        }
        now = 0;
        vis[1] = true;
        father[1] = 1;
        DFS(1);
        printf("%d\n",Greedy());
    }

    return 0;
}