最小生成树:

关于最小生成树的基本定理:

1. 任意一棵最小生成树一定包含无向图中权值最小的边.
2. 给定一张无向图 $G = (V, E)$ , 从 $E$ 中选出 $k < n - 1$ 条边构成的 $G$ 的一个生成森林, 若再从剩余的 $m - k$ 条边中选 $n - 1 - k$ 条添加到生成森林中, 使其成为 $G$ 的生成树,并且选出的边的权值之和最小,则该生成树一定包含这 $m - k$ 条边中连接生成森林的两个不连通的节点的权值最小的边.

AcWing 1146. 新的开始 原题链接

算法思路 :

图论中常用的假设虚拟原点问题, 假设一个虚拟原点, 到点 $i$ 的边的权值为在该点建立电站$v_{i}$, 求一个包含所有点的最小生成树.

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 310;

int g[N][N];
int v[N];
int n;
int dist[N];
int st[N];

int prim()
{
    memset(dist, 0x3f, sizeof dist);
    dist[n + 1] = 0;
    int res = 0;
    for (int i = 0; i <= n; i ++ ){
        int t = -1;

        for (int j = 1; j <= n + 1; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        st[t] = 1;

        if (i)
            res += dist[t];

        for (int j = 1; j <= n + 1; j ++ )
            dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}


int main()
{
    cin >> n;

    for (int i = 1; i <= n; i ++ )
        cin >> v[i];

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            cin >> g[i][j];
    for (int i = 1; i < n + 1; i ++ )
        g[n + 1][i] = g[i][n + 1] = v[i];

    g[n + 1][n + 1] = 0;

    cout << prim() << endl;

    return 0;
}

AcWing 1145. 北极通讯网络 原题链接

算法思路:

图中有 $n$ 个点, 有 $n*n$ 条路径. 假设起始状态都不连通, 即有 $n$ 个连通块, 根据kruakal算法,每次找到一个边权值最小的点, 把该点加入到生成树中, 直到剩余 $k$ 个连通块, 我们可以直接用卫星连通.

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

using namespace std;
typedef pair<int,int> PII;
const int N = 510, M = N * N;
int n, k;

struct Edge{
    int a, b;
    double v;

    bool operator < (const Edge &t)const
    {
        return v < t.v;
    }
}edge[M];
PII p[N];
int fa[N];

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

double get_len(PII a, PII b)
{
    double dx = a.first - b.first;
    double dy = a.second - b.second;
    return sqrt(dx * dx + dy * dy);
}

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ ){
        cin >> p[i].first >> p[i].second;
        fa[i] = i;
    }

    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ ){
            double v = get_len(p[i], p[j]);
            edge[cnt ++] = {i,j,v};
        }

    sort(edge, edge + cnt);


    double ans = 0;
    int block = n;
    for (int i = 0; i < cnt; i ++ ){
        int aa = find(edge[i].a);
        int bb = find(edge[i].b);
        double v = edge[i].v;
        if (block == k)
            break;
        ans = v;

        if (aa != bb){
            block --;
            fa[aa] = bb;
        }


    }

    printf("%.2f", ans);

    return 0;
}

AcWing 346. 走廊泼水节 原题链接

算法思路:

完全图 : 完全图是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连.

题目要求: 满足图的唯一最小生成树仍然是原树, 同时, 要求所加权值之和最小.
每次将两个连通块通过已有边连接时, 需要将两个连通块中的点都连一条边, 数量为 $size[a] * size[b] - 1$ ,同时满足所加边权均为 $v + 1$ (同时满足权值最小和生成树唯一).

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 6010;

struct Edge{
    int a, b, v;
    bool operator < (const Edge &t)const
    {
        return v < t.v;
    }
}e[N];
int fa[N];
int s[N];
int n;

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

int main()
{
    int t;
    cin >> t;
    while (t -- ){
        cin >> n;
        for (int i = 1; i < n; i ++ ){
            int a, b, v;
            cin >> a >> b >> v;
            e[i] = {a, b, v};
        }

        sort(e + 1, e + n);

        int res = 0;
        for (int i = 1; i <= n; i ++ ){
            fa[i] = i;
            s[i] = 1;
        }

        for (int i = 1; i < n; i ++ ){
            int a = find(e[i].a);
            int b = find(e[i].b);
            int v = e[i].v;

            if (a != b){
                res += (s[a] * s[b] - 1) * (v + 1); 
                s[b] += s[a];
                fa[a] = b;
            }
        }
        cout << res << endl;
    }

    return 0;
}