Pagini recente » Borderou de evaluare (job #2704162) | Borderou de evaluare (job #976282) | Cod sursa (job #1845258)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define NMax 200005
#define MMax 400005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int N,M;
struct Edges{ int x,y,z; } Edge[MMax];
int rank[NMax],father[NMax];
int totalCost;
vector<pair<int,int> > sol;
void Read();
void Write();
inline bool cmp(Edges a,Edges b)
{
return a.z<b.z;
}
int GetRoot(int x)
{
int root;
for(root=x;root!=father[root];root=father[root]);
return root;
}
void Unite(int x,int y)
{
if(rank[x]>rank[y])
father[y]=x;
else
father[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
void APM()
{
for(int i=1;i<=M;i++)
{
int x=Edge[i].x;
int y=Edge[i].y;
int rootx=GetRoot(x);
int rooty=GetRoot(y);
if(rootx!=rooty)
{
Unite(rootx,rooty);
sol.push_back(make_pair(Edge[i].x,Edge[i].y));
totalCost+=Edge[i].z;
}
}
}
int main()
{
Read();
for(int i=1;i<=N;i++)
{
rank[i]=i;
father[i]=i;
}
sort(Edge+1,Edge+M+1,cmp);
APM();
Write();
return 0;
}
void Read()
{
fin>>N>>M;
for(int i=1;i<=M;i++)
{
fin>>Edge[i].x>>Edge[i].y>>Edge[i].z;
}
}
void Write()
{
fout<<totalCost<<"\n";
fout<<sol.size()<<"\n";
for(vector<pair<int,int> >::iterator it=sol.begin();it!=sol.end();it++)
fout<<it->first<<" "<<it->second<<"\n";
}