图论——最小生成树的扩展应用

假设存在一个“超级发电站”
在每一个矿井修发电站相当于从这个“超级发电站”到各个矿井连一条长度为$v[i]$的边。
这样一来这就是一个最短路的模板题。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 310;
int dist[N];
bool st[N];
int w[N][N];
int n;
int prim()
{
    memset(dist, 0x3f, sizeof dist);
    dist[0] = 0;
    int res = 0;
    for (int i = 0; i < n + 1; i ++ )
    {
        int t = -1;
        for (int j = 0; j < n + 1; j ++ )
        {
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        st[t] = 1;
        res += dist[t];
        for (int j = 0; j < n + 1; j ++ )
            dist[j] = min(dist[j], w[t][j]);
    }
    return res;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> w[0][i];
        w[i][0] = w[0][i];
    }
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            cin >> w[i][j];
    printf("%d", prim());
    return 0;
}

假设有给定一个$d$值，将任意两个长度小于等于$d$的点都进行集合合并，形成$m$个连通块($m$ 棵最小生成树)，则需要$m$个卫星设备
即找一个最小的$d$值，使得将所有权值大于$d$的边删去，之后，整个图形的连通块的个数等于$k$。

显然，连通块的数量和d取值会满足以下这种关系。

我们考虑kruskal算法，kruskal算法是从大到小枚举每个边，如果该边两端不连通则加入该边，当我们当前枚举的边权为d时，虽然实际上我们只是在小于等于d的边权中选择将能够实现联通的边加入了最小生成树生成了若干连通块，然而实际上这和把边权小于等于d的边全部连起来形成连通块的情况是相同的，也正因此我们上面这个问题和kruskal算法实际上是等价的，我们可以用kruskal算法来做。

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N = 510, M = N * N / 2;
int fa[N];
int m = 0, cnt;
struct Edge{
    int a, b;
    double w;
    bool operator< (const Edge &t) const{
        return w < t.w;
    }
}e[M];
PII q[N];
int n, k;
double get_dist(PII a, PII b)
{
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}
int find(int a)
{
    return fa[a] == a ? a : fa[a] = find(fa[a]);
}
int main()
{
    double res = 0;
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ )
        fa[i] = i;
    for (int i = 1; i <= n; i ++ )
        cin >> q[i].x >> q[i].y;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j < i; j ++ )
            e[++ m] = {i, j, get_dist(q[i], q[j])};
    cnt = n;
    sort(e + 1, e + m + 1);
    for (int i = 1; i <= m; i ++ )
    {
        int a = find(e[i].a), b = find(e[i].b);
        double w = e[i].w;
        if (cnt <= k) break;
        if (a == b) continue;
        fa[a] = b;
        res = w;
        cnt -- ;
    }
    printf("%.2lf\n", res);
    return 0;
}

做法：初始时先将每一个点看成一个大小为1的连通块，这个连通块就可以看成一个完全图(因为只有一个点)
做Kruskal算法，在每循环到一条可以合并两个连通块的边$e$时，记$e$的边长为$w$,为了形成一个完全图，就要使得两个已经是完全图的连通块中的点有边，但是为了使最后的唯一最小生成树还是原来那棵而且，新增的边一定要大于$w$：
假设新边小于$w$，因为新增边后会成环，当断开边$e$，形成的树大小会变小，即不是原来那棵，所以不成立
假设新边等于$w$，同样的断开$e$，会形成一个大小一样但结构不一样的树，不满足唯一，所以也不成立。
这里我们新增的边权可以为$w+1$，因为我们的边权为从小到大枚举，也正因此$w+1$不会影响左右两个连通块内部最小生成树的情况。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 6010, M = N * N / 2;
int fa[N];
int sz[N];
struct Edge{
    int a, b, w;
    bool operator< (const Edge &t) const{
        return w < t.w;
    }
}e[M];
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int t;
int main()
{
    cin >> t;
    while (t -- )
    {
        int n;
        cin >> n;
        for (int i = 1; i < n; i ++ )
        {
            int a, b, w;
            cin >> a >> b >> w;
            e[i] = {a, b, w};
        }
        sort(e + 1, e + n);
        for (int i = 1; i <= n; i ++ )
        {
            sz[i] = 1;
            fa[i] = i;
        }
        int res = 0;
        for (int i = 1; i < n; i ++ )
        {
            int a = find(e[i].a), b = find(e[i].b), w = e[i].w;
            if (a == b) continue;
            res += (sz[a] * sz[b] - 1) * (w + 1);
            sz[b] += sz[a];
            fa[a] = b;
        }
        cout << res << endl;
    }
    
    return 0;
}

次小生成树的求解方式：

题解来源：https://www.acwing.com/solution/content/80131/

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 510, M = 10010;
struct Edge{
    int a, b, w;
    bool flag;
    bool operator< (const Edge &t) const{
        return w < t.w;
    }
}edge[M];
int fa[N];
int n, m;
int dist1[N][N], dist2[N][N];
int h[N], e[2 * N], ne[2 * N], w[2 * N], tot;
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void add(int a, int b, int c)
{
    e[tot] = b, ne[tot] = h[a], w[tot] = c, h[a] = tot ++ ;
}
void dfs(int u, int fa, int maxd1, int maxd2, int d1[], int d2[])
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        if (w[i] > maxd1)
        {
            d1[j] = w[i], d2[j] = maxd1;
            dfs(j, u, w[i], maxd1, d1, d2);
        }
        else if (w[i] < maxd1 && w[i] > maxd2)
        {
            d1[j] = maxd1, d2[j] = w[i];
            dfs(j, u, maxd1, w[i], d1, d2);
        }
        else{
            d1[j] = maxd1, d2[j] = maxd2;
            dfs(j, u, maxd1, maxd2, d1, d2);
        }
    }
    return ;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i ++ )
    {
        int a, b, w;
        cin >> a >> b >> w;
        edge[i] = {a, b, w};
    }
    for (int i = 1; i <= n; i ++ )
        fa[i] = i;
    sort (edge + 1, edge + 1 + m);
    memset(h, -1, sizeof h);
    ll sum = 0;
    for (int i = 1; i <= m; i ++ )
    {
        int a = edge[i].a, b = edge[i].b, w = edge[i].w;
        int aa = find(a), bb = find(b);
        if (aa != bb)
        {
            fa[aa] = bb;
            sum += w;
            edge[i].flag = 1;
            add(a, b, w), add(b, a, w);
        }
    }
    for (int i = 1; i <= n; i ++ )
        dfs(i, -1, 0, 0, dist1[i], dist2[i]);
    ll res = 1e18;
    for (int i = 1; i <= m; i ++ )
    {
        if (edge[i].flag) continue;
        int a = edge[i].a, b = edge[i].b, w = edge[i].w;
        if (w > dist1[a][b]) res = min(res, sum + w - dist1[a][b]);
        else if (w > dist2[a][b]) res = min(res, sum + w - dist2[a][b]);
    }
    cout << res;
    return 0;
}