最短网络

kruskal + Prim

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

using namespace std;

const int N = 200, M = 1e6 + 10;

int n, k = 0;
int g[N][N];
int f[N],dist[N];
bool v[N];

struct Edge
{
    int x, y, w;
    bool operator <(Edge &e)const
    {
        return w < e.w;
    }
}edges[M];

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

int Kruskal()
{
    for(int i = 1; i <= n; i ++ )
        f[i] = i;
    int res = 0, cnt = 0;
    for(int i = 0; i < k; i ++ )
    {
        int x = edges[i].x, y = edges[i].y, w = edges[i].w;
        int fx = find(x), fy = find(y);
        if(fx != fy)
        {
            cnt ++;
            res += w;
            f[fy] = fx;    
        }
        if(cnt == n - 1)    return res;
    }
}

int Prim()
{
    memset(dist, 0x3f, sizeof dist);

    int res = 0;
    for(int i = 1; i <= n; i ++ )
    {
        int t = -1;
        for(int j = 1; j <= n; j ++ )
        {
            if(!v[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        v[t] = true;

        if(i != 1) res += dist[t];
        if(i != 1 && dist[t] == 0x3f3f3f3f)  return 0x3f3f3f3f;

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

    return res;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 1; j <= n; j ++ )
        {
            scanf("%d", &g[i][j]);
            edges[k++] = {i, j, g[i][j]};
        }
    }

    sort(edges, edges + k);

    int t = Kruskal();

    printf("%d", t);
    return 0;
}