Cod sursa(job #2278875)

Utilizator vladuteluVlad Oancea vladutelu Data 8 noiembrie 2018 17:42:06
Problema Arbore partial de cost minim Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

FILE*in = fopen("apm.in", "r");
FILE*out = fopen("apm.out", "w");

int T[200002];
vector<int> v[200002];
bool seen[200002];

int find_daddy(int x)
{
	if(x!=T[x])
		T[x]=find_daddy(T[x]);
	return T[x];
}

void join(int x, int y)
{
	int t1=find_daddy(x);
	int t2 = find_daddy(y);
	T[t2]=t1;
}

struct muchie
{
	int nod1;
	int nod2;
	int cost;
};

muchie muc[400001];

bool cmp(muchie a, muchie b)
{
	if(a.cost < b.cost)
		return 1;
	return 0;
}

int main()
{
    int n, m, c, x, y, cost = 0, nrm = 0;
    fscanf(in, "%d %d", &n, &m);
    for(int i = 1; i<=n; i++)
		{
			T[i]=i;
		}
    for(int i = 1; i<=m; i++)
		{
			fscanf(in, "%d %d %d", &x, &y, &c);
			muc[i].nod1 = x;
			muc[i].nod2 = y;
			muc[i].cost = c;
		}
		sort(muc+1, muc+m+1, cmp);
		int i = 1;
		while(nrm!=n-1)
		{
			int nod1, nod2;
			nod1 = muc[i].nod1;
			nod2 = muc[i].nod2;
			if(find_daddy(nod1) != find_daddy(nod2))
			{
				join(nod1, nod2);
				v[nod1].push_back(nod2);
				v[nod2].push_back(nod1);
				cost+=muc[i].cost;
				nrm++;
			}
			i++;
		}

		fprintf(out, "%d\n", cost);
		fprintf(out, "%d\n", n-1);
		for(int i = 0; i<n; i++)
		{
			for(int j = 0; j<v[i].size();j++)
				if(i<v[i][j])
					fprintf(out, "%d %d\n", i, v[i][j]);
		}
		fclose(in);
		fclose(out);
    return 0;
}