树的最小支配集，最小点覆盖，最大独立集两种算法

1.基本概念

对图G=<V,E>,

最小支配集：从V中取尽量少的点组成一个集合，使得V中剩余的点都与取出来的点有边相连

最小点覆盖：从V中取尽量少的点组成一个集合，使得E中所有边都与取出来的点相连

最大独立集：从V中取尽量多的点组成一个集合，使得这些点之间没有边相连

2.贪心法求树的最小支配集，最小点覆盖，最大独立集模板

基本算法：

以最小支配集为例，首先选择一点为根，按照深度优先遍历得到遍历序列，按照所得序列的反向序列的顺序进行贪心，对于一个既不属于支配集也不与支配集中的点相连的点来说，如果他的父节点不属于支配集，将其父节点加入支配集。

struct Edge
{
    int v,next;
}G[M];

int fa[N];
int vis[N];
int pos[N],head[N];
int now;
int n,m;

void DFS(int u)
{
    pos[now++] = u;
    for(int i=head[u];i!=-1;i=G[i].next)
    {
        int v = G[i].v;
        if(!vis[v])
        {
            vis[v] = 1;
            fa[v] = u;
            DFS(v);
        } 
    }
}

int MDS()
{
    int s[N] = {0};
    int set[N] = {0};
    int ans = 0;
    for(int i=now-1;i>=0;i--)
    {
        int t = pos[i];
        if(!s[t])
        {
            if(!set[fa[t]])
            {
                set[fa[t]] = 1;
                ans++;
            }
            s[t] = 1;
            s[fa[t]] = 1;
            s[fa[fa[t]]] = 1;
        }
    }
    return ans;
}

最小支配集MDS

int MPC()
{
    int s[N] = {0};
    int set[N] = {0};
    int ans = 0;
    for(int i=now-1;i>=0;i--)
    {
        int t = pos[i];
        if(!s[t] && !s[fa[t]])
        {
            set[fa[t]] = 1;
            ans++;
            s[t] = 1;
            s[fa[t]] = 1;
        }
    }
    return ans;
}

最小点覆盖MPC

int MIS()
{
    int s[N] = {0};
    int set[N] = {0};
    int ans = 0;
    for(int i=now-1;i>=0;i--)
    {
        int t = pos[i];
        if(!s[t])
        {
            set[t] = 1;
            ans++;
            s[t] = 1;
            s[fa[t]] = 1;
        }
    }
    return ans;
}

最大独立集MIS

void MDS_DP(int u,int fa) { dp[u][2] = 0; dp[u][0] = 1; int s = 0; int sum = 0; int inc = Mod; for(int i=head[u];i!=-1;i=G[i].next) { int v = G[i].v; if(v == fa) continue; MDS_DP(v,u); dp[u][0] += min(dp[v][0],min(dp[v][1],dp[v][2])); if(dp[v][0] <= dp[v][1]) { sum += dp[v][0]; s = 1; } else { sum += dp[v][1]; inc = min(inc,dp[v][0]-dp[v][1]); } if(dp[v][1] != Mod && dp[u][2] != Mod) dp[u][2] += dp[v][1]; else dp[u][2] = Mod; if(inc == Mod && !s) //i没有子节点 dp[u][1] = Mod; else { dp[u][1] = sum; if(!s) dp[u][1] += inc; } } }

void MPC_DP(int u,int fa) { dp[u][0] = 1; dp[u][1] = 0; for(int i=head[u];i!=-1;i=G[i].next) { int v = G[i].next; if(v = fa) continue; MPC_DP(v,u); dp[u][0] += min(dp[v][0],dp[v][1]); dp[u][1] += dp[v][0]; } }

void MIS_DP(int u,int fa) { dp[u][0] = 1; dp[u][1] = 0; for(int i=head[u];i!=-1;i=G[i].next) { int v = G[i].v; if(v == fa) continue; MIS_DP(v,u); dp[u][0] += dp[v][1]; dp[u][1] += max(dp[v][0],dp[v][1]); } }

树的最小支配集，最小点覆盖，最大独立集两种算法

相关推荐