Go: package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

type ElementKey int
type Node struct {
	key    ElementKey
	parent *Node
	rank   int
}

func newNode(key ElementKey) *Node {
	node := Node{}
	node.key = key
	node.parent = &node
	node.rank = 0

	return &node
}

func union(x, y *Node) {
	xSet := findSet(x)
	ySet := findSet(y)
	link(xSet, ySet)
}

func link(x, y *Node) {
	if x.rank > y.rank {
		y.parent = x
	} else {
		x.parent = y

		if x.rank == y.rank {
			y.rank++
		}
	}
}

func findSet(x *Node) *Node {
	if x != x.parent {
		x.parent = findSet(x.parent)
	}
	return x.parent
}

func newDisjointSets(nSets int) *DisjointSets {
	sets := DisjointSets{}
	sets.keyToNode = map[ElementKey]*Node{}
	for i := 0; i < nSets; i++ {
		key := ElementKey(i)
		sets.keyToNode[key] = newNode(key)
	}
	return &sets
}

type DisjointSets struct {
	keyToNode map[ElementKey]*Node
}

func (sets *DisjointSets) union(x, y ElementKey) {
	xNode := sets.keyToNode[x]
	yNode := sets.keyToNode[y]
	union(xNode, yNode)
}

func (sets DisjointSets) findSet(x ElementKey) *Node {
	xNode := sets.keyToNode[x]
	return findSet(xNode)
}

type Edge struct {
	i, j   int
	weight int
}

func main() {
	scanner.Split(bufio.ScanWords)

	n := nextInt()
	sets := newDisjointSets(n)
	edges := []Edge{}
	a := make([][]int, n)
	for i := 0; i < n; i++ {
		a[i] = make([]int, n)
		for j := 0; j < n; j++ {
			a[i][j] = nextInt()
			if a[i][j] >= 0 {
				e := Edge{
					i:      i,
					j:      j,
					weight: a[i][j],
				}
				edges = append(edges, e)
			}
		}
	}
	sort.Slice(edges, func(i, j int) bool { return edges[i].weight < edges[j].weight })
	totalWeight := 0
	for _, edge := range edges {
		i := ElementKey(edge.i)
		j := ElementKey(edge.j)
		if sets.findSet(i) != sets.findSet(j) {
			totalWeight += edge.weight
			sets.union(i, j)
		}
	}
	fmt.Println(totalWeight)
}

C++: #include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>

using namespace std;

#define REP(var, count) for(int var=0; var<count; var++)

struct unionf {
	
	vector<int> data;
	
	unionf(int n) {
		REP(i, n+1) { data.push_back(i); }
	}
	
	int root(int a) {
		if(data[a] == a) { return a; }
		return (data[a] = root(data[a]));
	}
	
	bool issame(int a, int b) {
		return root(a) == root(b);
	}
	
	void unite(int a, int b) {
		data[root(a)] = root(b);
	}

};

int main(void) {
	int N;
	cin >> N;
	
	vector<pair<int, pair<int, int> > > edge;
	
	REP(x, N) {
		REP(y, N) {
			int c;
			cin >> c;
			if ( x <= y ) { continue; }
			if ( c == -1 ) { continue; }
			edge.push_back( make_pair(c, make_pair(x,y)) );
		}
	}
	
	sort(edge.begin(), edge.end());
	
	unionf uf(N);
	
	int cnt = 0;
	int ret = 0;
	REP(i, edge.size() ) {
		
		pair<int, int> sd = edge[i].second;
		if ( ! uf.issame( sd.first, sd.second ) ) {
			cnt ++;
			ret += edge[i].first;
		}
		
		if ( cnt == N-1 ) { break; }
	}
	
	cout << ret << endl;
}

C++: #include<iostream>
using namespace std;
#define S 100
#define INF 2001
#define WHITE 0;
#define GRAY 1;
#define BLACK 2
int n,a[S][S];

int prim(){
    int u,mina;
    int d[S],p[S],cnd[S];

    for(int i=0;i<n;i++){
        d[i]=INF;
        p[i]=-1;
        cnd[i]=WHITE;
    }

    d[0]=0;
    while(1){
        mina=INF;
        u=-1;
        for(int i=0;i<n;i++){
            if(mina>d[i]&&cnd[i]!=BLACK){
                u=i;
                mina=d[i];
            }
        }
        if(u==-1)break;
        cnd[u]=BLACK;
        for(int v=0;v<n;v++){
            if(cnd[v]!=BLACK&&a[u][v]!=INF){
                if(d[v]>a[u][v]){
                    d[v]=a[u][v];
                    p[v]=u;
                    cnd[v]=GRAY;
                }
            }
        }
    }
            int sum=0;
        for(int i=0;i<n;i++){
            if(p[i]!=-1)sum+=a[i][p[i]];
        }
    return sum;
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int e;
            cin>>e;
            if(e==-1)a[i][j]=INF;
            else a[i][j]=e;
        }
    }
    cout<<prim()<<endl;
    return 0;

}

C++: #include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
using namespace std;

#if 0
所用時間: 1h

感想: 思ったより実装すべきコード量が多かった。DisjointSetは今後も使う機会が多そうなので、クラス化してみた。
Pの配列を動的に確保するよう工夫した、良い復習になった。

#endif

int N, buff, M = 0, SUM = 0, A[101][101], cost[5000], dpt[5000], dst[5000];//A[Y][X]
vector<pair<int, int> > edges;

class disjointSet {
private:
    int* P;
    
public:
    disjointSet(){
        P = new int[100000];
    }
    disjointSet(int N){     
        P = new int[N];
    }
    ~disjointSet(){
        delete[] P;
    }

    void init(int N){ //木構造の初期化
        for(int i = 0; i <= N; ++i){
            P[i] = i;
        }
    }

    int root(int a){ //根の参照
        if(P[a] == a) return a;
        return (P[a] = root(P[a]));
    }

    bool is_same_set(int a, int b){ //同じ根か?
        return root(a) == root(b);
    }

    void unite(int a, int b){
        P[root(a)] = root(b); //aのrootをbの子にする
    }
};


void preprocess(){//辺の前処理
  for(int r = 0; r < N; ++r){
    for(int c = r+1; c < N; ++c){
      if (A[r][c] > -1) {
        cost[M] = A[r][c];
        dpt[M] = r;
        dst[M] = c;
        M++;
      }
    }
  }

  //for(int i = 0; i < M; ++i) cout << cost[i] << endl;

  for(int i = 0; i < M; ++i){
    edges.push_back(make_pair(cost[i], i));
  }
  for(int i = 0; i < M; ++i) cout << edges[i].first << " " << edges[i].second << endl;

  sort(edges.begin(), edges.end());

  for(int i = 0; i < M; ++i) cout << edges[i].first << " " << edges[i].second << endl;

}

void solve(){
  disjointSet Union(100000);

  int ans = 0;
  preprocess();

  Union.init(N);

  for(int i = 0; i < M; ++i){
    int index = edges[i].second;
    if(Union.is_same_set(dpt[index], dst[index])) continue;
    else {
      Union.unite(dpt[index], dst[index]);
      cout << "unite " << dpt[index] << " and " << dst[index] << endl;
      ans += cost[index];
    }
  }
  cout << ans << endl;
}

int main(){

cin >> N;

for(int i = 0; i < N; ++i){
  for(int j = 0; j < N; ++j){
    cin >> buff;
    A[i][j] = buff;
    }
  }

  //行列の表示
  // cout << "Matrix:" << endl;
  // for(int row=0; row < N; ++row){
  //   for(int col = 0; col < N; ++col){
  //     cout << A[row][col];
  //   }
  //   cout << endl;
  // }

  solve();
}

C++: #include<stdio.h>

int field[110][110];
int selected[110] = { 0 };
int v;

int prim()
{
	int no_edge = 0;
	int weight = 0;
	selected[0] = 1;
	int x, y;

	while (no_edge < v - 1)
	{
		int min = 0x7fffffff;
		for (int i = 0; i < v; i++)
		{
			if (selected[i])
				for (int j = 0; j < v; j++)
				{
					if (!selected[j] && field[i][j] != -1)
						if (min > field[i][j])
						{
							min = field[i][j];
							x = i;
							y = j;
						}
				}
		}
		weight += field[x][y];
		no_edge++;
		selected[y] = 1;
	}
	return weight;
}

int main()
{
	scanf("%d", &v);
	for (int i = 0; i < v; i++)
		for (int j = 0; j < v; j++)
			scanf("%d", &field[i][j]);
	printf("%d\n", prim());
}