问题描述

下面是一个8个结点的无向图的邻接矩阵表示，其中第 i 行第 j 列表示结点 i 到结点 j 的边长度。当长度为 0 时表示不存在边。
请问，这个图的最小生成树大小的多少？

样例

0 9 3 0 0 0 0 9
9 0 8 1 4 0 0 0
3 8 0 9 0 0 0 0
0 1 9 0 3 0 0 5
0 4 0 3 0 7 0 6
0 0 0 0 7 0 5 2
0 0 0 0 0 5 0 4
9 0 0 5 6 2 4 0

/*
  Kruskal算法
   kruscal算法是用于生成最小生成树的常见算法,
   最小生成树也就是在包含图中所有节点的树中,边权和最小的那棵树
        将所有的边长按从小到大排列，每次取最小的边连接两节点，
            若两节点已经处于连通状态，则不连接
                循环上面的步骤，知道所有节点都已经连通，所有边之和就是答案
*/

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

using namespace std;

const int n = 8;
int p[n],ans = 0;

vector<pair<int,int>> a;

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

int main()
{
    for(int i = 0;i < n ; i ++) p[i] = i;

    for(int i = 0 ; i < n ; i ++)
        for(int j = 0; j < n ; j ++)
        {
            int len;
            cin >> len;
            if(len) a.push_back({len,i * 100 + j});
        }
        sort(a.begin(),a.end());
        for(int i = 0 ; i < a.size() ; i ++)
        {
            int len = a[i].first;
            int x = a[i].second / 100;
            int y = a[i].second % 100;
            if(find(x) != find(y))
            {
                p[p[x]] = p[y];
                ans += len;
                printf("%d --> %d (%d)\n", x, y, len);
            }
        }

    cout << ans << endl;
    return 0;
}