USACO 3.1.1 – Agri-Net


#include <cstdio>
#include <queue>
using namespace std;
int parent[101];
struct E{ int a,b,w; };
bool operator <(const E& a, const E& b){ return a.w>b.w; }
int findset(int x){
    return parent[x] = ( x!=parent[x] ? findset(parent[x]) : parent[x]) ;
}
int main() {
	int N, g[101][101]={{0}}, c=0;
	priority_queue<E> q;
	freopen("agrinet.in", "r", stdin), freopen("agrinet.out", "w", stdout);
	scanf("%d", &N);
	for(int i=0; i<N; parent[i]=i, i++)
		for(int j=0; j<N; q.push(E{i, j, g[i][j]}), j++)
			scanf("%d", g[i] + j);

	while(q.size()){
		E e = q.top(); q.pop();
		int a = findset(e.a), b =findset(e.b);
		c+= a!=b ? e.w : 0, parent[b] = a;
	}

	printf("%d\n", c);
	return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: