POJ 3398 Perfect Service --最小支配集

这题可以用两种上述讲的两种算法解：http://www.cnblogs.com/whatbeg/p/3776612.html

第一种，贪心算法：

贪心算法直接套一个最小支配集模板就可以了，我不能证明这样是正确的，但是能AC

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define Mod 1000000007
using namespace std;
#define N 10007

struct Edge
{
    int v,next;
}G[2*N];

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

void addedge(int u,int v)
{
    G[tot].v = v;
    G[tot].next = head[u];
    head[u] = tot++;
}

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;
}

int main()
{
    int n,u,v,i,j;
    int op;
    while(scanf("%d",&n)!=EOF)
    {
        tot = 1;
        now = 0;
        memset(head,-1,sizeof(head));
        for(i=0;i<n-1;i++)
        {
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }
        memset(vis,0,sizeof(vis));
        memset(fa,-1,sizeof(fa));
        fa[1] = 1;
        DFS(1);
        int res = MDS();
        printf("%d
",res);
        scanf("%d",&op);
        if(op == -1)
            break;
    }
    return 0;
}

View Code

第二种，树形DP。因为此时由于一台电脑不能与多台服务器连接，所以直接DP转移求最小支配集有可能不是正确解。

状态设计与上篇的相同，但是注意dp[i][0]的转移方程中，不能有dp[i][1]，因为此时该子节点有一个子节点被选入最小支配集，而当前节点也被选入最小支配集，此时该子节点与两个支配集中的点相连，不符合题意。其他转移方式不变。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define Mod 1000000007
using namespace std;
#define N 10007

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

int head[N],tot;
int dp[N][3];

void addedge(int u,int v)
{
    G[tot].v = v;
    G[tot].next = head[u];
    head[u] = tot++;
}

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],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;
        }
    }
}

int main()
{
    int n,u,v,i,j;
    int op;
    while(scanf("%d",&n)!=EOF)
    {
        tot = 1;
        memset(head,-1,sizeof(head));
        for(i=0;i<n-1;i++)
        {
            scanf("%d%d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }
        for(i=0;i<=n;i++)
            for(j=0;j<=2;j++)
                dp[i][j] = Mod;
        MDS_DP(1,-1);
        int res = min(dp[1][0],dp[1][1]);
        printf("%d
",res);
        scanf("%d",&op);
        if(op == -1)
            break;
    }
    return 0;
}

View Code