树的最小支配集、最小点覆盖、最大独立集

最小支配集

定义：对于图 (G=(V,E)) ，最小支配集指的是从 (V) 中取尽量少的结点组成一个集合，使得 (V) 中剩余的点都与取出来的点有边相连。

解法：定义 dp 各状态意义如下：

(dp[u][0])：结点 (u) 属于支配集，并且 (u) 的子孙都被覆盖了的情况下支配集中包含的最少结点个数；
(dp[u][1])：结点 (u) 不属于支配集，并且 (u) 的子孙都被覆盖，(u) 也被不少于 1 个子结点覆盖的情况下支配集中包含的最少结点个数；
(dp[u][2])：结点 (u) 不属于支配集，并且 (u) 的子孙都被覆盖，(u) 没有被子结点覆盖的情况下支配集中包含的最少结点个数。

状态转移方程如下：

(dp[u][0]=1+sum_{vin son_u} min(dp[v][0],dp[v][1],dp[v][2])) ;
(if)(u没有子结点): (dp[u][1] = INF)

(else): (dp[u][1] = inc+sum_{vin son_u}min(dp[v][0],dp[v][1]))

对于 (inc) 有：

(if(exist vin son_u, dp[v][0]le dp[v][1]): inc=0)

(else: inc=min({dp[v][0]-dp[v][1] | vin son_u})) ;
(dp[u][2]=sum_{vin son_u}dp[v][1]) 。

代码实现：例题：nowcoder-24953 Cell Phone Network

#include <cstdio>
#include <algorithm>
using std::min;
const int maxn = 10010, INF = 0x3f3f3f3f;
int dp[maxn][3];
int head[maxn], to[maxn<<1], nex[maxn<<1], tot;
void add_edge(int u, int v) {
    to[++tot] = v;
    nex[tot] = head[u];
    head[u] = tot;
}
void dfs(int u, int fa) {
    dp[u][0] = 1;
    dp[u][1] = dp[u][2] = 0;
    int inc = INF;
    for (int i = head[u], v; i > 0; i = nex[i]) {
        v = to[i];
        if (v == fa) continue;
        dfs(v, u);
        dp[u][0] += min(dp[v][0], min(dp[v][1], dp[v][2]));
        if (dp[v][0] <= dp[v][1]) inc = 0;
        else if (inc) inc = min(inc, dp[v][0] - dp[v][1]);
        dp[u][1] += min(dp[v][0], dp[v][1]);
        if (dp[u][2] != INF && dp[v][1] != INF) dp[u][2] += dp[v][1];
        else dp[u][2] = INF;
    }
    dp[u][1] += inc;
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0, u, v; i < n - 1; i++) {
        scanf("%d %d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
    }
    dfs(1, -1);
    printf("%d
", min(dp[1][0], dp[1][1]));

    return 0;
}

最小点覆盖

定义：对于图 (G=(V,E)) ，最小点覆盖指的是从 (V) 中取尽量少的结点组成一个集合 (V')，使得 (E) 中所有的边 ((u,v)) 都满足 (uin V' or vin V') 。

解法：定义 dp 各状态的意义如下：

(dp[u][0])：表示 (u otin V') ，并且以 (u) 为根的子树中所有的边都被覆盖的情况下 (V') 中的最少结点数量；
(dp[u][1])：表示 (uin V')，并且以 (u) 为根的子树中所有的边都被覆盖的情况下 (V') 中的最少结点数量。

状态转移方程如下：

(dp[u][0] = sum_{vin son_u}dp[v][1]) ;
(dp[u][1]=1+sum_{vin son_u}min(dp[v][0],dp[v][1])) 。

代码实现：例题 nowcoder-106060 Strategicgame

#include <cstdio>
#include <cstring>
#include <algorithm>
using std::min;
const int maxn = 1510;
int dp[maxn][2];
int head[maxn], to[maxn<<1], nex[maxn<<1], tot;
void add_edge(int u, int v) {
    to[++tot] = v;
    nex[tot] = head[u];
    head[u] = tot;
}
void dfs(int u, int fa) {
    dp[u][0] = 0;
    dp[u][1] = 1;
    for (int i = head[u], v; i > 0; i = nex[i]) {
        v = to[i];
        if (v == fa) continue;
        dfs(v, u);
        dp[u][0] += dp[v][1];
        dp[u][1] += min(dp[v][0], dp[v][1]);
    }
}

int main() {
    int n;
    while (~scanf("%d", &n)) {
        memset(head, 0, sizeof(head));
        tot = 0;
        for (int i = 0; i < n; i++) {
            char s[15];
            scanf("%s", s);
            int u = 0, idx = -1, k = 0;
            while (s[++idx] != ':') u = u * 10 + s[idx] - '0';
            ++idx;
            while (s[++idx] != ')') k = k * 10 + s[idx] - '0';
            for (int j = 0, v; j < k; j++) {
                scanf("%d", &v);
                add_edge(u, v);
                add_edge(v, u);
            }
        }
        dfs(0, -1);
        printf("%d
", min(dp[0][0], dp[0][1]));
    }
    return 0;
}

最大独立集

定义：对于图 (G(V,E)) ，最大独立集指的是从 (V) 中取尽量多的结点组成一个集合，使得这些结点之间没有边相连。

解法：像最小点覆盖一样也是定义 (u) 是否属于独立集的两个 dp 状态，太简单了不写了。