Agri-Net

agrinet

Algorithm

This is a standard Minimum Spanning Tree problem. We run Kruskal's MST algorithm, with a disjoint-set union-find data structure to keep track of the connected components for a runtime of O(N^2 log N); it is complete overkill when N <= 100 but it sounds cool so I'm using it anyway.

C++

#include <bits/stdc++.h>
using namespace std;

void setio(string s) {
    freopen((s+".in").c_str(),"r",stdin);
    freopen((s+".out").c_str(),"w",stdout);
}

struct DSU {
    vector<int> e;
    DSU(int N) { e = vector<int>(N, -1); }
    int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
    bool same_set(int a, int b) { return get(a) == get(b); }
    int size(int x) { return -e[get(x)]; }
    bool unite(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return false;
        if (e[x] > e[y]) swap(x, y);
        e[x] += e[y]; e[y] = x; return true;
    }
};

int main() {
    setio("agrinet");
    int n;
    cin >> n;
    vector<tuple<int, int, int>> e;
    for (int i=0; i<n; ++i) {
        for (int j=0; j<n; j++) {
            int w;
            cin >> w;
            e.push_back({i,j,w});
        }
    }
    sort(
        e.begin(), e.end(),
        [](const tuple<int,int,int> & x, const tuple<int,int,int> & y) {
            return get<2>(x) < get<2>(y);
        }
    );
    long cost = 0;
    DSU dsu(n);
    for (int i=0; i<e.size(); ++i) {
        int a = get<0>(e[i]); int b = get<1>(e[i]);
        if (!dsu.same_set(a, b)) {
            cost += get<2>(e[i]);
            dsu.unite(a, b);
        }
    }
    cout << cost << endl;
}