問題概要

ジョン農場主が町長に選出されました！彼の選挙公約の一つは、町全体にインターネットを導入し、すべての農場を接続することです。もちろん、彼はあなたの助けが必要です。

ジョンはすでに自身の農場に高速ネットワーク回線を設置済みであり、これを他の農場と共有したいと考えています。費用を最小限に抑えるため、すべての農場を接続する最短の光ファイバーを敷設する必要があります。

農場間の接続費用リストが与えられるので、すべての農場を接続し、使用する光ファイバーの総長が最小になる方案を見つける必要があります。

任意の2つの農場間の距離は100000を超えません。

入力

ファイル agrinet.in からデータを読み込みます。
最初の行： 農場の数 N（3 <= N <= 100）。
2行目以降： N×Nの行列が続きます。各農場間の距離を表します。理論上はN行で、各行はN個のスペースで区切られた数字から構成されますが、実際には80文字に制限されているため、一部の行は他の行に続くことがあります。対角線要素は0です（i番目の農場から自身への接続は存在しないため）。

出力

ファイル agrinet.out に出力します。
すべての農場を接続するために必要な光ファイバーの最小長を1行で出力します。

サンプル入力

4

0 4 9 21

4 0 8 17

9 8 0 16

21 17 16 0

サンプル出力

28

実装コード：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct Edge {
    int weight;
    int source;
    int destination;
};

vector<int> parentSet;
vector<Edge> edgeList;

int findRoot(int node) {
    if (parentSet[node] != node) {
        parentSet[node] = findRoot(parentSet[node]);
    }
    return parentSet[node];
}

void uniteSets(int nodeA, int nodeB) {
    int rootA = findRoot(nodeA);
    int rootB = findRoot(nodeB);
    parentSet[rootB] = rootA;
}

int main() {
    // freopen("agrinet.in", "r", stdin);
    // freopen("agrinet.out", "w", stdout);
    
    int farmCount;
    cin >> farmCount;
    
    parentSet.resize(farmCount + 1);
    for (int i = 1; i <= farmCount; i++) {
        parentSet[i] = i;
    }
    
    for (int i = 1; i <= farmCount; i++) {
        for (int j = 1; j <= farmCount; j++) {
            int distance;
            cin >> distance;
            if (distance != 0 && i < j) {
                edgeList.push_back({distance, i, j});
            }
        }
    }
    
    sort(edgeList.begin(), edgeList.end(), [](const Edge &a, const Edge &b) {
        return a.weight < b.weight;
    });
    
    int totalWeight = 0;
    int edgesUsed = 0;
    
    for (const auto &edge : edgeList) {
        if (findRoot(edge.source) != findRoot(edge.destination)) {
            uniteSets(edge.source, edge.destination);
            totalWeight += edge.weight;
            edgesUsed++;
            
            if (edgesUsed == farmCount - 1) {
                break;
            }
        }
    }
    
    cout << totalWeight << endl;
    return 0;
}