Algorithm

USACO Section3.1 agrinet

Problem Summary

Given an undirected graph, find the weight of its minimum spanning tree.

Solution

Since the graph is dense, we choose Prim Algorithm over Kruskal Algorithm.
The graph is stored in adjacency matrix, so the time complexity is O(n^2).

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <fstream>
#include <cstring>
#include <climits>
using namespace std;
int n;
int dist[102][102],d[102];
bool vis[102];
int prim()
{
	for(int i=0;i<n;i++) d[i]=dist[0][i];
	int mind,k,ans=0;
	for(int i=0;i<n;i++)
	{
		mind=INT_MAX;
		for(int j=0;j<n;j++)
			if(!vis[j] && d[j]<mind)
			{
				mind=d[j];
				k=j;
			}
		if(mind==INT_MAX) break;
		vis[k]=true;
		ans+=mind;
		for(int j=0;j<n;j++)
			if(!vis[j] && d[j]>dist[k][j])
				d[j]=dist[k][j];
	}
	return ans;
}
int main()
{
	fstream fin("agrinet.in",ios::in);
	fstream fout("agrinet.out",ios::out);
	fin>>n;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			fin>>dist[i][j];
	fout<<prim()<<endl;
	fin.close();
	fout.close();
	return 0;
}