Pagini recente » Rezultatele filtrării | Rezultatele filtrării | Borderou de evaluare (job #1656339) | Cod sursa (job #1718813) | Cod sursa (job #2384575)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
#define nmax 400005
pair <int,int> P[nmax];
int n,m,suma_cost,t[nmax],rg[nmax],a1,a2,cont=0;
struct muchii
{
int x,y,cost;
}v[nmax];
bool comp(muchii a, muchii b)
{
return a.cost<b.cost;
}
int Find(int nod)
{
while(t[nod]!=nod)
nod=t[nod];
return nod;
}
void Union(int x, int y)
{
if(rg[x]<rg[y])
t[x]=y;
if(rg[y]<rg[x])
t[y]=x;
if(rg[x]==rg[y])
{
t[x]=y;
rg[y]++;
}
}
int main()
{
fin>>n>>m;
for(int i=1;i<=m;i++)
{
fin>>v[i].x>>v[i].y>>v[i].cost;
t[i]=i;
rg[i]=1;
}
sort(v+1,v+1+m,comp);
for(int i=1;i<=m;i++)
{
if(Find(v[i].x)!=Find(v[i].y))
{
a1=Find(v[i].x);
a2=Find(v[i].y);
Union(a1,a2);
cont++;
P[cont].first=v[i].x;
P[cont].second=v[i].y;
suma_cost+=v[i].cost;
}
}
fout<<suma_cost<<endl;
fout<<n-1<<endl;
for(int i=1;i<=cont;i++)
fout<<P[i].first<<" "<<P[i].second<<endl;
}