最小支配集
2019-08-18
RT
1.支配集(DS,dominating set)？
支配集的定义如下：给定无向图G =（V , E）,其中V是点集， E是边集， 称V的一个子集S称为支配集当且仅当对于V-S中任何一个点v, 都有S中的某个点u, 使得(u, v) ∈E。
2.最小支配集(MDS)?
对于图G = (V, E) 来说,最小支配集指的是从 V 中取尽量少的点组成一个集合, 使得 V 中剩余的点都与取出来的点有边相连.也就是说,设 V' 是图的一个支配集,则对于图中的任意一个顶点 u ,要么属于集合 V', 要么与 V' 中的顶点相邻. 在 V' 中除去任何元素后 V' 不再是支配集, 则支配集 V' 是极小支配集.称G 的所有支配集中顶点个数最少的支配集为最小支配集,最小支配集中的顶点个数称为支配数.
tip:以上定义有点青涩难懂，但是康康几道例题就可以明白了
Slove
贪心策略
首先选择一点为树根,再按照深度优先遍历得到遍历序列,按照所得序列的反向序列的顺序进行贪心,对于一个即不属于支配集也不与支配集中的点相连的点来说,如果他的父节点不属于支配集,将其父节点加入到支配集
具体实现
1.设整型数组dfn,fa,布尔数组vis,st。dfn[i]表示dfs中出现的第i个节点，fa[i]表示dfs中节点i的父节点，vis[i]-false表示节点i不属于支配集也不与支配集中的点相连，st[i]-true表示节点i在MDS中。
2.建图（邻接表）。
3.dfs一遍树，确定dfn,fa。
4.dfn逆序查找，确定vis,st,同时得出MDS。
Tip：
1.Code中的代码，读者需根据题目的具体情况具体改动。
2.听闻如此求MDS,时间复杂度为O（n）?
3.听闻MSD还有树状DP的做法，但是蒟蒻的我不会。
4.以上部分内容抠自度娘。
5.但是度娘的代码太诡异了。
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 10010
using namespace std; //标准开头
int ans; //ans-MDS的点数
int first[N],next[N*2],len,to[N*2];
int dfn[N],cnt,fa[N];
bool vis[N],st[N];
void add(int u,int v){ //邻接表建图
to[++len]=v;
next[len]=first[u];
first[u]=len;
}
void dfs(int s,int f){
dfn[++cnt]=s;
fa[s]=f;
for(int i=first[s];i!=-1;i=next[i]) if(to[i]!=f) dfs(to[i],s);
}
void MDS(){
for(int i=n;i>=1;i--){
int s=dfn[i];
if(!vis[s]){ //不属于支配集也不与支配集中的点相连的点
if(!st[fa[s]]){ //父节点不属于支配集
st[fa[s]]=true; //其父节点加入到支配集
ans++;
}
vis[s]=true;
vis[fa[s]]=true;
vis[fa[fa[s]]]=true;
}
}
}
int main()
{
// 建图 //
dfs(1,1);
MDS();
return 0;
}