Cod sursa(job #693271)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 27 februarie 2012 11:33:20
Problema Arbore partial de cost minim Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const char iname[] = "apm.in";
const char oname[] = "apm.out";

ifstream fin(iname);
ofstream fout(oname);

vector<pair <int, int> > Gr[400006];
int n, m, i, x, y, c, k, sum;
int tree[400006];
int sol[400006];
int father[400006];

struct edge
{
	int cp1, cp2, cost;
}muchie[400000];

struct cmp
{
	bool operator()(const edge &a, const edge &b)const
	{
		if(a.cost < b.cost)
			return 1;
		return 0;
	}
};

int tata(int nod)
{
	if(father[nod] != nod)
		return tata(father[nod]);
	else
		return nod;
}



int main()
{
	fin >> n >> m;
	for(i = 1; i <= m; i ++)
	{
		fin >> x >> y >> c;
		Gr[x].push_back(make_pair(y, c));
		muchie[i].cp1 = x, muchie[i].cp2 = y, muchie[i].cost = c;
	}
	
	sort(muchie + 1, muchie + m + 1, cmp());
	for(i = 1; i <= n; i ++)
		father[i] = i;
	
	for(i = 1; i <= m; i ++)
	{
		if(tata(muchie[i].cp1) != tata(muchie[i].cp2))
		{
			sol[++k] = i;
			sum = sum + muchie[i].cost;
			father[tata(muchie[i].cp1)] = tata(muchie[i].cp2);
		}
	}
	
	fout << sum << "\n";
	fout << k << "\n";
	for(i = 1; i <= k; i ++)
		fout << muchie[sol[i]].cp1 << " " << muchie[sol[i]].cp2 << "\n";
	return 0;
}