三.最小生成树的应用

最小生成树+最短路

黑暗城堡

题目中要求的是一颗最短路径生成树。

首先，我们可以跑一遍最短路，即根节点 \(1\) 到节点 \(i\) 的最短距离为 \(dis_i\)。

那么 \(ans=\prod_{i=2}^n num(dis[i]=dis[j]+edge[i,j])\)。

即在所有 \(i\) 能到达的点中，若 \(dis[i]=dis[j]+edge[i,j]\)，就将 \(sum_i+1\)，最终的答案就是所有 \(sum\) 的乘积。

原理：当两点构成最短路径时，随便选哪个点都可以，根据乘法原理，答案就是所有选择的乘积。

最后一个问题，这和最小生成树有什么关系：

1. 这道题的本质是求最短路径生成树。
2. 这道题的原理与 prim 类似。

#include 
#include 
#include 
#include 
#include 
#include 
#define N 1010
#define M 1000000
const long long MOD = 2147483647;
using namespace std;

int n, m, dis[N], head[N], cnt = 0;
bool vis[N];
struct Edge {
    int nxt, to, val;
} edge[M];
priority_queue > q;

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}

void addedge(int x, int y, int z) {
    cnt++;
    edge[cnt].nxt = head[x];
    edge[cnt].to = y;
    edge[cnt].val = z;
    head[x] = cnt;
    return;
}

void dij() {
    memset(dis, 0x7f, sizeof(dis));
    memset(vis, false, sizeof(vis));
    dis[1] = 0;
    q.push(make_pair(0, 1));
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = head[u]; i; i = edge[i].nxt) {
            int v = edge[i].to, w = edge[i].val;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push(make_pair(-dis[v], v));
            }
        }
    }
    return;
}

int main() {
    n = read();
    m = read();
    int x, y, z;
    for (int i = 1; i <= m; i++) {
        x = read();
        y = read();
        z = read();
        addedge(x, y, z);
        addedge(y, x, z);
    }
    dij();
    long long ans = 1;
    for (int i = 2; i <= n; i++) {
        int sum = 0;
        for (int j = head[i]; j; j = edge[j].nxt)
            if (dis[i] == dis[edge[j].to] + edge[j].val)
                ++sum;
        ans = (ans * sum) % MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

最小生成树+逆向思维

北极通讯网络

吐槽一下：正解是最小生成树，但是有一种比正解好太多的方法竟然看不到有人用，可见书籍对大家思维的禁锢。

神犇就当我什么都没说。

正解就是靠逆向思维呀，下面是标准的证明：

当正向思考受阻时，逆向思维可能有奇效，本题就是这样。

知道卫星设备的数量，求最小的收发距离，可能比较困难；如果知道距离求数量，就很简单了。

把所有可以互相通讯的村庄连接起来，构成一个图。卫星设备的台数就是图的连通支的个数。

问题转化为：找到一个最小的d，使得把所有权值大于d的边去掉之后，连通支的个数小于等于k。

先看一个定理：如果去掉所有权值大于d的边后，最小生成树被分割成为k个连通支，图也被分割成为k个连通支。

证明：用反证法。假设原图被分割成 k’ (k'≠k) 个连通支，显然不可能 k’>k，所以 k’

因此在某一图的连通支中，最小生成树被分成了至少两部分，不妨设其为T1,T2。

因为T1和T2同属于一个连通支，所以一定存在x∈T1，y∈T2，w(x,y)≤d。

又因为在整个最小生成树中，所以x到y的路径中一定存在一条权值大于d的边(u,v)（否则x和y就不会分属于T1和T2了），w(x,y)≤d

所以把(x,y)加入，把(u,v)去掉，将得到一棵总权值比最小生成树还小的生成树。

这显然是不可能的。所以，原命题成立。（证毕）

有了这个定理，很容易得到一个构造算法：最小生成树的第k长边就是问题的解。

首先，d取最小生成树中第k长的边是可行的。如果d取第k长的边，我们将去掉最小生成树中前k-1长的边，最小生成树将被分割成为k部分。由定理，原图也将分割成为k部分。（可行性）

其次，如果d比最小生成树中第k长的边小的话，最小生成树至少被分割成为k+1部分，原图也至少被分割成为k+1部分。与题意不符。（最优性）

综上所述，最小生成树中第k长的边是使得连通支个数≤k的最小的d，即问题的解。

大把大把的文字啊...。

以下是标程：

#include 
#define re register
using namespace std;
const int maxn = 500 + 10;
int fa[maxn], x[maxn], y[maxn], n, k;
struct node {
    int l, r;
    double dis;
} sid[maxn * maxn];
double tre[maxn];
inline double d(int x1, int x2, int y1, int y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
inline bool cmp(node a, node b) { return a.dis < b.dis; }
inline int fnd(int i) {
    if (fa[i] != i)
        fa[i] = fnd(fa[i]);
    return fa[i];
}
int main() {
    scanf("%d%d", &n, &k);
    if (k >= n) {
        printf("0.00\n");
        return 0;
    }
    for (re int i = 1; i <= n; ++i) {
        fa[i] = i;
        scanf("%d%d", &x[i], &y[i]);
    }
    int s = 0;
    for (re int i = 1; i <= n; ++i)
        for (re int j = i + 1; j <= n; ++j) sid[++s] = (node){ i, j, d(x[i], x[j], y[i], y[j]) };
    sort(sid + 1, sid + 1 + s, cmp);
    int num = 0;
    for (re int i = 1; i <= s; i++) {
        int a = fnd(sid[i].l), b = fnd(sid[i].r);
        if (a != b) {
            tre[++num] = sid[i].dis;
            fa[a] = b;
        }
    }
    printf("%.2lf", tre[num - k + 1]);
    return 0;
}

由于 sort 排序花费了大把时间，所以时间复杂度为 \(O(n^2\ log\ n^2)\)。

然后想一想我的方法，既然要求最小，显然可以二分答案。

范围？\([0,\sqrt {10^4\times 10^4+10^4\times 10^4}]\approx[0,20000]\)。

将每一条 \(\leq mid\) 的边联通，当连通块个数 \(\leq k\) 时可行。

时间复杂度：\(O(n^2)\)。（\(log\ 20000\approx 15\)，可以忽略）

而且不仅时间少，空间也小很多，码量也小一点点...。（似乎这才是正解？）

#include 
#include 
#include 
#include 
#include 
#define N 510
using namespace std;

int n, m, fa[N];
struct node {
    double x, y;
} a[N];

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}

bool dis(int x, int y, double mx) {
    double fx = a[x].x - a[y].x;
    double fy = a[x].y - a[y].y;
    return fx * fx + fy * fy <= mx * mx;
}

int find(int x) {
    if (fa[x] == x)
        return x;
    return fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    fa[find(x)] = find(y);
    return;
}

bool chck(double k) {
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++)
            if (dis(i, j, k))
                merge(i, j);
    }
    int sum = 0;
    for (int i = 1; i <= n; i++)
        if (fa[i] == i)
            ++sum;
    return sum <= m;
}

int main() {
    n = read();
    m = read();
    for (int i = 1; i <= n; i++) scanf("%lf %lf", &a[i].x, &a[i].y);
    double l = 0.0, r = 20000.0, mid, eps = 1e-5;
    while (r - l > eps) {
        mid = (l + r) / 2;
        if (chck(mid))
            r = mid;
        else
            l = mid;
    }
    printf("%.2lf\n", r);
    return 0;
}

最小生成树+构造

新的开始

类似于分层图的构造思想，既然每个节点都可以选择连线或建造发电站，就建立节点 \(0\) 表示发电站。

将每一个点建造发电站的费用变为与 \(0\) 号节点的边权，结果就变为求增加了一个点的最小生成树。

注意一： \(0\) 号节点只能连接单向的 \(0\to i\) 的边，因为如果连双向边，就有可能两个点 \(i\to 0\to j\) 这样到达。

这种方案的实际意义是：两个点分别建两座发电站，然后两点就联通了，显然这是不可能的呀。

注意二：这里是完全图的最小生成树，显然用 prim 更优。

#include 
#include 
#include 
#include 
#include 
#define N 310
#define maxd 999999999
using namespace std;

int n, e[N][N], dis[N];
bool vis[N];

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}

void prim() {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, false, sizeof(vis));
    dis[0] = 0;
    for (int i = 0; i < n; i++) {
        int mn = maxd, k;
        for (int j = 0; j <= n; j++)
            if (!vis[j] && dis[j] < mn) {
                mn = dis[j];
                k = j;
            }
        vis[k] = true;
        for (int j = 1; j <= n; j++)
            if (!vis[j])
                dis[j] = min(dis[j], e[k][j]);
    }
    return;
}

int main() {
    n = read();
    int v;
    for (int i = 1; i <= n; i++) v = read(), e[0][i] = v;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) e[i][j] = read();
    prim();
    int ans = 0;
    for (int i = 0; i <= n; i++) ans += dis[i];
    printf("%d\n", ans);
    return 0;
}

最小生成树+贪心

构造完全图

构造没有头绪？

来考虑 Kruscal 的原理：贪心的选最小的边并连接两点所在的连通块。

同样的，这里考虑贪心，将最小生成树的边权由小到大排序并做一遍 Kruscal，同时记录下连通块的大小。

记 \(cnt_i\) 为端点 \(i\) 所在连通块的大小，那么每次连边就令 \(ans+=(cnt_i+cnt_j-1)\times (edge_{i,j}+1)\)。

解释一下，为什么是 \(cnt_i+cnt_j-1\)，因为除了最小生成树上的那条边以外，所有边都要连接。

为了使边权最小但是又不能 \(>edge_{i,j}\)，贪心的选择肯定是都赋值为 \(edge_{i,j}+1\) 最小。

同时，不要忘记 \(ans+=\sum_{i=1}^{n-1} edge_{i.val}\)，也就是加上原本的最小生成树上的边。

#include 
#include 
#include 
#include 
#include 
#define N 100010
#define int long long
using namespace std;

int n, cnt[N], fa[N];
long long ans = 0;
struct node {
    int x, y, z;
} a[N];

int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}

bool cmp(node a, node b) { return a.z < b.z; }

int find(int x) {
    if (fa[x] == x)
        return x;
    return fa[x] = find(fa[x]);
}

signed main() {
    n = read();
    for (int i = 1; i < n; i++) a[i].x = read(), a[i].y = read(), a[i].z = read(), ans += a[i].z;
    sort(a + 1, a + n, cmp);
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        cnt[i] = 1;
    }
    for (int i = 1; i < n; i++) {
        int fx = find(a[i].x);
        int fy = find(a[i].y);
        if (fx != fy) {
            ans += (cnt[fx] * cnt[fy] - 1) * (a[i].z + 1);
            fa[fy] = fx;
            cnt[fx] += cnt[fy];
        }
    }
    printf("%lld\n", ans);
    return 0;
}

四.最小生成树计数

最小生成树计数

为什么单独拿出来讲这个计数呢？因为这个东东比较重要。（主要是让我们明白了一个定理）

每一个最小生成树相同边权的边的数量相等。（很重要的定理，一定要记住）

证明：我也不会。

有了这个定理就好办了，就只要用乘法原理将每一条边的可能的方案数相乘即可，现在问题在于怎么求方案数。

显然，某一种边权的边可以成为方案的前提是：

1. 数量与之前的最小生成树中的数量一样。（根据定理）
2. 没有与之前的边相连形成环。（根据最小生成树的定义）

由于数据感人（相同边数 \(\leq 10\)），所以可以暴力 DFS 来统计方案数。（即每条边选或不选）

最坏时间复杂度：\(O(2^{10}m)\)，但是实际上远远达不到这个时间，而且就算达到了也不会超时，所以能过。

然后建议大家去康康 dalao 的题解，蒟蒻我不懂什么是 Matrix_Tree 定理...。

#include
#include
#include
#include
#include
#include
#define N 110
#define M 1010
#define MOD 31011
using namespace std;

int n,m,fa[N],sum=0,ans=1,tot=0;
struct Edge{
	int x,y,z;
}edge[M];
struct node{
	int l,r,cnt;
}f[M];

int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0' || c>'9') f=(c=='-')?-1:1,c=getchar();
	while(c>='0' && c<='9') x=x*10+c-48,c=getchar();
	return x*f;
}

bool cmp(Edge a,Edge b){return a.z