时间复杂度:

$$ prim : O(n^2) $$

$$ kruskal : O(mlogm) $$

例题:

A.繁忙都市

$prim$ 和 $kruskal$ 均可

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

using namespace std;

const int N = 301,M = 100010;

int n ,m;
int fa[N];
int res ,cnt;
struct road
{
    int a ,b ,w;
    bool operator < (const road &x) const
    {
        return x.w > w;
    }
}e[M];

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

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> e[i].a >> e[i].b >> e[i].w;

    sort(e + 1 , e + m + 1);

    for (int i = 1; i <= n; i++) fa[i] = i;

    for (int i = 1; i <= m; i ++)
    {
        int a = find(e[i].a),b = find(e[i].b),w = e[i].w;
        if (a != b)
        {
            fa[a] = b;
            res = max(res , w);
            cnt ++;
            if (cnt == n - 1)
            {
                cout << cnt << ' ' << res;
                return 0;
            }
        }
    }
    return 0;
}

B.新的开始

解题思路：建一个超级源点n + 1，n + 1到各个节点的距离就是各个节点单独建一个发电站的费用

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

using namespace std;

const int N = 310;

int n;
int g[N][N];
int dis[N];
int vis[N];

int main() {
    cin >> n;
    memset(g, 0x3f, sizeof g);
    memset(dis, 0x3f, sizeof dis);
    for (int i = 1; i <= n; i++) {
        cin >> g[i][n + 1];
        g[n + 1][i] = g[i][n + 1];
    }

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

    for (int i = 1; i <= n + 1; i++) dis[i] = g[1][i];

    int res = 0;

    for (int i = 1; i <= n; i++) {
        int now = 0;
        for (int j = 0; j <= n + 1; j++)
            if (!vis[j] && dis[j] < dis[now])
                now = j;
        res += dis[now];
        for (int j = 1; j <= n + 1; j++) dis[j] = min(dis[j], g[now][j]);

        vis[now] = true;
    }
    cout << res;
    return 0;
}

C.公路建设

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

using namespace std;

const int N = 5005;

int n ,m ,cnt;
int fa[N];
struct way
{
    int a ,b ,w;
}e[N];

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

void work(way x)
{
    for (int i = 1; i <= n; i++) fa[i] = i;

    e[++ cnt] = x; // 先加一条边进来
    for (int i = cnt; i >= 1; i --) // 因为这是一条一条加进来的，故一重循环就可以（保证边权升序）
        if (e[i].w < e[i - 1].w)
            swap(e[i] , e[i - 1]);

    int k = 0,res = 0;
    for (int i = 1; i <= cnt; i ++) 
    {
        int a = find(e[i].a),b = find(e[i].b),w = e[i].w;
        if (a != b) // 如果不连通
        {
            fa[a] = b;
            res += w;
        }
        else k = i; // i是要删去的边(这里直接删去不要判断谁大谁小的原因是边权已经是升序的了)
    }
    if (k) // 如果可以删
    {
        cnt --;
        for (int i = k; i <= cnt; i ++) // 把要删的点放到最后
            swap(e[i] , e[i + 1]);
    }

    if (cnt != n - 1) puts("0"); // 如果没连通
    else printf ("%.1lf\n",res / 2.0); // 题目说了50%
    return ;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i ++)
        cin >> e[i].a >> e[i].b >> e[i].w;
    for (int i = 1; i <= m; i ++)
        work(e[i]);
    return 0;
}

D.构造完全图

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

using namespace std;

const int N = 100010;

typedef long long LL;

int n;
int sum[N];
int fa[N];
struct edge
{
    int a ,b ,w;
}e[N];

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

bool cmp(edge x,edge y)
{
    return x.w < y.w;
}

int main()
{
    cin >> n;
    for (int i = 1; i < n; i++)
        cin >> e[i].a >> e[i].b >> e[i].w;

    sort(e + 1 , e + n , cmp);

    for (int i = 1; i <= n; i ++ ) fa[i] = i,sum[i] = 1;

    LL 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 = res + (LL)(sum[a] * sum[b] - 1) * (w + 1);
        // 如果不连通,则还需连sum[a] * sum[b] - 1个点  且边权最小为w + 1(因为如果比w小，则这个最小生成树就是错误的)
        sum[a] += sum[b];
        fa[b] = a;
        sum[b] = 0;
        res += w;
        // 当然，最后还要加上最小生成树上的点
    }
    cout << res;
    return 0;
}

E.连接云朵

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

using namespace std;

const int N = 1001,M = 10010;

int n ,m ,k;
int fa[N];

struct edge
{
    int a , b, w;
}e[M];

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

bool cmp(edge x,edge y)
{
    return x.w < y.w;
}

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i ++)
        cin >> e[i].a >> e[i].b >> e[i].w;

    sort(e + 1 , e + m + 1 , cmp);

    for (int i = 1; i <= n; i ++) fa[i] = i;

    int cnt = 0,res = 0;
    for (int i = 1; i <= m; i++)
    {
        int a = find(e[i].a),b = find(e[i].b),w = e[i].w;
        if (a != b)
        {
            cnt ++;
            fa[a] = b;
            res += w;
        }
        if (cnt == n - k) // 这里是n - k 不是 k - 1
        {
            printf ("%d",res);
            return 0;
        }
    }
    puts("No Answer");
    return 0;
}

G.生物进化

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

using namespace std;

const int N = 101;

int n;
int g[N][N] ,d[N] ,a[N];
bool vis[N];

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

    d[1] = 0;
    for (int i = 1; i <= n; i++) d[i] = g[1][i] ,a[i] = 1;

    vis[1] = true;

    for (int i = 1; i <= n; i++)
    {
        int now;
        int minn = 0x3f3f3f3f; // 还是定义一个minn吧(针对自己说)
        for (int j = 1; j <= n; j++)
            if (!vis[j] && d[j] < minn)
                minn = d[j],now = j;

        vis[now] = true;

        for (int j = 1; j <= n; j++)
        {
            if (d[j] > g[now][j] && !vis[j])
            {
                d[j] = g[now][j];
                a[j] = now;
            }
        }
    }
    for (int i = 2; i <= n; i ++ ) cout << a[i] << endl;
    return 0;
}