生成树相关问题（一）

最小生成树

对于无向图 $G(V, E)$ 的切割 $(S, V-S)$ 是集合 $V$ 的一个划分，如果边 $(u, v)$
一个端点位于 $S$，另一个端点位于 $V-S$，称为该边横跨切割 $(S, V-S)$

如果集合 $A$ 中不存在横跨切割的边，那么称切割尊重集合 $A$
在横跨切割的所有边中，权值最小的边称为轻量级边

定理 不妨设集合 $A$ 为 $E$ 的一个子集，并且 $A$ 包括在图 $G$ 的某棵最小生成树中
设切割 $(S, V-S)$ 尊重集合 $A$，又设 $(u, v)$ 是横跨切割 $(S, V-S)$ 的一条轻量级边
那么边 $(u, v)$ 对于集合 $A$ 是安全的，可以执行 $A \leftarrow A \cup \{(u, v)\}$

证明，假设原图中的最小生成树为 $T$，边 $(u, v)$ 与 $T$ 中 $u \to v$ 的简单路径 $p$ 构成环路
$u, v$ 分别位于切割 $(S, V-S)$ 的两端，在 $p$ 中可以找到一条边 $(x, y)$，使得 $(x, y)$ 横跨 $(S, V-S)$
因为切割 $(S, V-S)$ 尊重集合 $A$，所以 $(x, y) \notin A$，由此可以构造出新的生成树

$$T' = T - \{(x, y)\} \cup \{(u, v)\}$$

由于边 $(u, v)$ 横跨切割 $(S, V-S)$ 并且是一条轻量级边，$(x, y)$ 也横跨切割，所以
$w(u, v) \leqslant w(x, y)$

$$w(T') = w(T) - w(x, y) + w(u, v) \leqslant w(T)$$

$T$ 是最小生成树，那么 $T'$ 也一定是最小生成树

下面再证明 $(u, v)$ 是一条安全边，因为 $A \subseteq T$ 并且 $(x, y) \notin A$，所以
$A \subseteq T- \{(x, y)\}$，由于 $T' = T - \{(x, y)\} \cup \{(u, v)\}$，所以 $A \cup \{(u, v)\} \subseteq T'$
$T'$ 是最小生成树，所以 $(u, v)$ 是安全的

kruskal and prim

kruskal 和 prim 算法都是基于上述思想实现的

Kruskal 算法
kruskal 算法实现起来比较简单

• 初始化并查集，此时每个点各自是一个集合
• 将所有的边从小到大排序，扫描每一条边 $(u, v)$
• 如果 $\text{find}(u) = \text{find}(v)$，忽略这一条边
  否则的话合并 $u, v$ 所在的集合，并且将 $w(u, v)$ 累加到答案 $\text{ans}$ 中

const int maxn = 1e5 + 10;
int n, m, pa[maxn];
struct Edge {
    int x, y, z;
} edges[maxn];

int kruskal() {
    for (int i = 0; i <= n; i++) pa[i] = i;
    function<int(int)> get = [&](int x) {
        return x == pa[x] ? x : pa[x] = get(pa[x]);
    };

    sort(edges+1, edges+1+m, [](const Edge& a, const Edge &b) {
        return a.z < b.z;
    });

    int ans = 0;
    for (int i = 1; i <= m; i++) {
        int x = get(edges[i].x), y = get(edges[i].y);
        if (x == y) continue;
        pa[x] = y, ans += edges[i].z;
    }
    return ans;
}

Prim 算法
Prim 算法需要用到轻量级边的定义，实现过程类似分层图
由于最小生成树有 $n-1$ 条边，所以需要加入 $n-1$ 条轻量级边
需要一个 $d(y)$ 数组，当 $y \in S$ 时，$d(y)$ 表示 $(y, x)$ 横跨切割 时， $y$ 作为起点的最小边权
$y \in T$ 时，$d(y)$ 表示边 $(x, y)$ 横跨切割时，以 $y$ 作为终点的边的最小边权

• 维护两个集合 $S, T$，其中 $S$ 是已经确定的最小生成树集合，$T$ 是剩下的集合
• 接着执行 $n-1$ 次循环，添加轻量级边，对于每一次的循环，扫描所有点
  找到不在 $S$ 中的点 $x$，其中 $d(x)$ 必须是最小的，将其加入集合 $S$
  之后更新横跨切割的边 $(x, y)$，即更新 $x$ 的所有出边，即 $d(y) = \min(d(y), w(x, y))$

执行完 Prim 算法之后，$\displaystyle\sum_{i = 1}^{n} d(i)$ 才是最小生成树的总权值
因为 $d(y)$ 保存的是每一条横跨切割的轻量级边

时间复杂度为 $O(n^2)$，主要用于稠密图

void prim() {
    memset(d, inf, sizeof d);
    memset(inq, 0, sizeof inq);

    d[1] = 0;
    for (int i = 1; i < n; i++) {
        int x = 0;
        for (int j = 1; j <= n; j++) {
            if (!inq[j] && (x == 0 || d[j] < d[x])) x = j;
        }
        inq[x] = 1;
        for (int y = 1; y <= n; y++) {
            if (!inq[y]) d[y] = min(d[y], G[x][y]);
        }
    }
}

prim 执行完成之后
int res = 0;
for(int i = 1; i <= n; i++) res += d[i];

res 是最小生成树

走廊泼水节
将图扩充为完全图，并且最小生成树不变，假设最小生成树轻量级边的权值为 $z$
那么添加的边权值应该 $> z$ 并且尽可能小，添加的边权设为 $z+1$ 即可

在执行 kruskal 算法时，对于边 $(x, y)$，合并 $x$ 所在的集合 $S(x)$ 和 $y$ 所在集合 $S(y)$ 时
根据乘法原理，一共有 $S(x) \cdot S(y)$ 条不同的横跨切割的边，（两个集合任选一个点）
除去最小生成树中的轻量级边保持不变，一共要添加 $(S(x)\cdot S(y) - 1) \cdot (w(x, y) + 1)$
将这个值累加到答案中即可

野餐规划

给定一个无向图，求满足 $1$ 号节点的度数不超过给定整数 $S$

• 如果去掉 $1$ 号节点，并且用 $\text{dfs}$ 求出连通块，连通块个数为 $T$
  $T > S$ 显然无解，因为最小生成树定义必须包括所有节点
  求连通块的时候可以标记节点 $u$ 属于连通块 $b(u)$
• 对于每一个连通块 $cc$，执行 $\text{calc}(cc)$，在连通块内部求出最小生成树
  具体来说，执行 kruskal 算法时，只考虑边 $(x, y)$，满足 $b(x) = b(y) = cc$
  这里还可以求出边 $(1, u)$，其中 $u \in cc$ 并且 $w(1, u)$ 权值最小
  将 $(1, u)$ 也加入到生成树中

经过以上处理，已经得到了节点 $1$ 度数为 $T$ 的最小生成树，在计算的时候，如果 $(u, v)$ 在生成树中
标记 $\text{used}(u, v) = 1$，以上初步得到最小生成树答案为 $\text{ans}$

那么剩下 $S-T$ 个点可以和 $1$ 连，还可能使得答案更优，对于边 $(1, x)$，权值为 $z$
如果 $(1, x)$ 不在最小生成树中，从 $1$ 开始沿着最小生成树路径走到 $x$，得到最大边权记为 $\text{maxcost}$
那么 $\text{ans}' = \text{ans} - (\text{maxcost} - z)$
此时可以用 $(1, x)$ 替换 $\text{maxcost}$ 的边，使得生成树更优
当且仅当 $\text{maxcost} - z > 0$ 并且 $\text{maxcost} - z$ 尽量大时成立

思路就有了，我们循环执行 $S-T$ 次，对于每一次操作，先对现有生成树执行 $\text{dfs}$
求出 $1 \to x$ 沿着最小生成树路径走，经过的最大权边 $\text{maxcost}(x)$（其中 $x$ 不在最小生成树上）
然后每次循环执行的时候，尝试添加一条不在原生成树中的边 $(1, x)$，这样的边应该如何选择呢？
很显然必须选择满足 $d(x) = \text{maxcost}(x) - w(1, x)$，$d(x) > 0$ 且 $d(x)$ 最大的 $(1, x)$
令 $ans \leftarrow ans - d$，还要记得标记 $\text{used}(1, x) = 1$
并且清除 $\text{maxcost}$ 的那条边 $(u, v)$，$\text{used}(u, v) = 0$
如果能找到的最大的 $d$ 都 $< 0$，直接退出循环

具体到算法实现上，最小生成树经常需要求解如下问题
$\text{path}: 1 \to x$ 沿着最小生成树路径走，所经过的最大的边，记为 $\text{maxe}[x]$
求解过程是基于动态规划的，$\text{dfs}(u, maxe)$，对于边 $(u, v)$
如果 $(u, v)$ 在最小生成树路径上，那么检查

• $w(u, v) < maxe[u].z$，那么 $maxe[v] \leftarrow maxe[u]$
• $w(u, v) >= maxe[u].z$，更新 $maxe[v] = Edge\{u, v, w(u, v)\}$

vector<Edge> maxe(maxn);
vector<int> vis(maxn);
void dfs(int u, vector<Edge>& maxe) {
    vis[u] = 1;
    for (auto v : G[u]) {
        if (!used[u][v] || vis[v]) continue;

        if (g[u][v] < maxe[u]) maxe[v] = maxe[u];
        else maxe[v] = Edge{u, v, g[u][v]};

        dfs(v, maxe);
    }
}

调用之前记得清空 maxe 和 vis

0-1分数规划问题

0-1 分数规划问题可以用小数二分来求解，具体来看
最优比率生成树

每条边有成本 $C_e$ 和长度 $L_e$，求生成树 $T$ 满足 $\displaystyle \frac{\displaystyle\sum_{e\in T} C_e}{\displaystyle\sum_{e\in T}L_e}$ 取到最小值

实际上可以二分答案，其实就是求满足 $\displaystyle \frac{\displaystyle\sum_{e\in T} C_e}{\displaystyle\sum_{e\in T}L_e} \geqslant mid$ 恒成立的 $mid$
其中 $l = 0, r = \displaystyle\frac{M \cdot \max\{C_e\}}{M \cdot \min\{L_e\}}$，所以 $r = 1000.0$，然后进行小数二分

算法执行的过程如下，二分要满足 $\displaystyle\sum_{e\in T}C_e \geqslant mid \cdot \sum_{e \in T}L_e$
实际上对于每条边，有 $C_e - mid \cdot L_e \geqslant 0$，建图的时候，只需要把每条边的权值设为 $C_e - mid \cdot L_e$ 即可
二分的判断过程如下

• 如果 $\sum C_e - mid \cdot \sum L_e \geqslant 0$，实际上等价于 $\sum C_e - mid \cdot \sum L_e$ 最小值都要 $\geqslant 0$
  在图上执行最小生成树 $\text{prim}(mid) \geqslant 0$，此时 $mid$ 是一个可行解，并且尝试继续增大 $mid$，令 $l = mid$
• 否则的话，令 $r = mid$，二分结束后，$l$ 就是答案

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cassert>

using namespace std;

#define fill_v(f, v) fill(f.begin(), f.end(), v)

const int maxn = 1000 + 10;
const double inf = 3e8;
const double eps = 1e-6;
int n;

struct V {
    double x, y, h;
};
vector<V> v(maxn, V());
double gRe[maxn][maxn], gLe[maxn][maxn];

inline double dist(int i, int j) {
    return sqrt( (v[i].x-v[j].x)*(v[i].x-v[j].x) + (v[i].y-v[j].y)*(v[i].y-v[j].y) );
}

bool prim(double mid) {
    vector<double> d(maxn, inf);
    vector<int> inq(maxn, 0);

    d[1] = 0;
    for (int i = 0; i < n-1; i++) {
        int x = 0;
        for (int j = 1; j <= n; j++) {
            if (!inq[j] && (x == 0 || d[j] < d[x])) x = j;
        }
        inq[x] = 1;

        for (int y = 1; y <= n; y++) {
            if (!inq[y] && d[y] > gRe[x][y] - mid * gLe[x][y] + eps) d[y] = gRe[x][y] - mid * gLe[x][y];
        }
    }
    double ans = 0.0;
    for (int i = 1; i <= n; i++) {
        assert(d[i] != inf);
        ans += d[i];
    }
    return ans >= 0 ? 1 : 0;
}

void solve() {
    double l = 0.0, r = 1000.0;
    while (l + eps < r) {
        double mid = (l + r) / 2.0;
        if (prim(mid)) l = mid;
        else r = mid;
    }
    printf("%.3lf\n", l);
}

void init() {
    fill_v(v, V());
    memset(gRe, 0, sizeof gRe), memset(gLe, 0, sizeof gLe);
}

int main() {
    //freopen("input.txt", "r", stdin);
    while (scanf("%d", &n) == 1 && n) {
        init();
        for (int i = 1; i <= n; i++) {
            double x, y, z;
            scanf("%lf%lf%lf", &x, &y, &z);
            v[i] = V{x, y, z};
        }

        // build
        for (int i = 1; i <= n; i++) {
            for (int j = i+1; j <= n; j++) {
                double Re = abs(v[i].h - v[j].h);
                double Le = dist(i, j);

                gRe[i][j] = gRe[j][i] = Re;
                gLe[i][j] = gLe[j][i] = Le;
            }
        }

        // solve
        solve();
    }
}

最短路径生成树

黑暗城堡

不难想到这是一个最短路树问题，从源点 $1$ 开始执行 $\text{dijkstra}$ 并且得到距离向量 $f[\cdots]$
$(x, y)$ 是最短路树上的边当且仅当 $f(y) = f(x) + e(x, y)$

可以根据 $\text{prim}$ 算法的思想，设计出如下算法

• 根据点 $i \in [1\cdots n]$ 的 $f(i)$ 排序，一开始令集合 $T$ 中只有一个元素 $1$，即 $\text{inq}(1) = 1$
• 枚举所有的节点 $\forall x \in [1\cdots n]$，找到第一个不在 $T$ 中的节点 $x$，即 $\text{inq}(x) = 0$ 的点，并初始化 $cnt = 0$
  接下来需要统计出 $T$ 中有多少个点 $p$ 满足 $d(x) = d(p) + (p, x)$，满足的话就令 $cnt++$
• 根据乘法原理，令 $res = res \cdot cnt$，然后把 $x$ 加入 $T$ 中，即 $\text{inq}(x) = 1$
  执行完之后，$res$ 就是答案

子图的最小生成树

北极网络

如果没有通信卫星的话，那么很显然 $D$ 是原图 $G = (N, M)$ 最小生成树中权值最大的边

现在有 $S$ 个通信卫星，实际上是求 $G$ 的一个子图 $G' = (N-S)$，即子图中有 $N-S$ 个点
同时还必须满足子图 $G'$ 的生成树 $T'$ 尽量小，生成树中权值最大的边就是所求的 $D$

最小生成树证明中，有一个结论
图 $G(N, M)$ 的最小生成树，一定包括权值最小的 $N-1$ 条边
那么子图 $G'$ 的最小生成树一定包括最小的 $N-S-1$ 条边

可以这么设计算法，执行 $\text{kruskal}$ 的时候，对边从小到大排序，并初始化 $cnt = 0$，当并查集 $x \neq y$ 时
令 $pa[x] = y, \ cnt++$，当 $cnt = N-S$ 的时候，此时边 $e$ 的权值就是答案

说明，此时维护的子图有 $N-S$ 个节点，有 $N-S-1$ 条边，另外还需要一条边连到“带有卫星的节点”
即子图外的节点，所以总共是最小的 $N-S$ 条边

四叶草魔杖

根据 $1 \leqslant N \leqslant 16$，很容易想到这一定是一个状态压缩
$0$ 表示宝石还未被处理，$1$ 表示已经被处理，那么起始状态为 $(00\cdots 0)$，终态为 $(11\cdots 1)$
令 $S = (1 \ll n) - 1$，从 $dp(0) \to dp(S)$，$dp(S)$ 就是答案

涉及枚举子集的操作，比如枚举 $S$ 的子集 $S_0$，代码如下

for (int S = 1; S < (1<<n); S++) {
    dp[S] = 初始化
    for (int S0 = S; S0; S0 = (S0-1) & S) {
        dp[S] = max(dp[S], dp[S^S0] + f(S0))
        // 其中 f(S0) 是将 S0 并入集合中的代价
    }
}

回到该问题，对于某一状态 $S$，它之前的状态假设为 $S'$，那么要考虑 $S' \to S$ 新加入了哪些元素？
刚刚加入的元素一定是 $S$ 的一个子集，可以考虑枚举子集 $S_0$，状态转移方程如下
$dp(S) = \min (dp(S), dp(S \oplus S_0) + f(S_0))$，其中 $f(S_0)$ 是将 $S_0$ 并入集合的最小代价

接下来需要考虑 $f(S_0)$ 怎么求，首先 $S_0$ 必须合法，也就是说新加入的元素 $i$，$\sum_{i} A_i = 0$
这很简单，对 $S_0$ 中为 $1$ 的每一位 $i$ 求 $sum = \displaystyle\sum_{i} A_i$
如果 $sum = 0$ 才合法，否则的话不合法

将 $S_0$ 为 $1$ 的位取出来，假设有 $C$ 个为 $1$ 的位，求出这些位能量转移的最小代价，就是 $f(S_0)$
而这又是一个部分点的最小生成树问题，只需要将 $m$ 条边按权值排序，然后依次检查每一条边
对于边 $(x, y)$，只有 $S_0$ 中表示 $x, y$ 的位同时为 $1$ 的时候，将边权值累加到结果中
另外注意，累加的时候记得统计生成树边的个数 $cnt$，只有 $cnt = C-1$ 的时候才合法

至此，先预处理 $f(S)$，然后执行 $dp$，$dp((1 \ll n)-1)$ 就是答案