贪心法求树的最小支配集
定义:
支配集:形式上,支配集可描述如下:给定无向图G =〈V , E〉,其中V 是大小为n 的点集,E 是边集,那么V 的一个子集S称为支配集当且仅当对于V - S 中任何一个点v ,都有S 中的某个定点u , 使得( u , v) ∈E。
最小支配集:对于图G = (V, E) 来说,最小支配集指的是从 V 中取尽量少的点组成一个集合, 使得V 中剩余的点都与取出来的点有边相连.也就是说,设 V' 是图的一个支配集,则对于图中的任意一个顶点 u ,要么属于集合 V', 要么与V' 中的顶点相邻. 在 V' 中除去任何元素后 V' 不再是支配集, 则支配集 V' 是极小支配集.称G 的所有支配集中顶点个数最少的支配集为最小支配集,最小支配集中的顶点个数称为支配数.
树形DP(点这里)
贪心策略:
思路:首先选择一点为树根,再按照深度优先遍历得到遍历序列,按照所得序列的反向序列的顺序进行贪心,对于一个即不属于支配集也不与支配集中的点相连的点来说,如果他的父节点不属于支配集,将其父节点加入到支配集.
代码实现:
例题:(点这里)vector实现
#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;
}