Pagini recente » Cod sursa (job #1979529) | Cod sursa (job #3192578)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie{
int x, y, c, val;
}l[400001];
bool cmp(muchie a, muchie b)
{
return a.c<b.c;
}
int tata[200001];
int getroot(int nod)
{
while(tata[nod]>0)
{
nod=tata[nod];
}
return nod;
}
int main()
{
int n, m, i, sol=0;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>l[i].x>>l[i].y>>l[i].c;
l[i].val=0;
}
for(i=1;i<=n;i++)
{
tata[i]=-1;
}
sort(l+1, l+m+1, cmp);
int nr=0;
i=1;
while(nr!=n-1)
{
int x=l[i].x;
int y=l[i].y;
int cost=l[i].c;
int rx=getroot(x);
int ry=getroot(y);
if(rx!=ry)
{
if(tata[rx]<tata[ry])
{
tata[rx]+=tata[ry];
tata[ry]=rx;
}
else
{
tata[ry]+=tata[rx];
tata[rx]=ry;
}
nr++;
sol+=cost;
l[i].val=1;
}
i++;
}
fout<<sol<<"\n"<<nr<<"\n";
for(i=1;i<=m;i++)
{
if(l[i].val==1)
{
fout<<l[i].x<<" "<<l[i].y<<"\n";
}
}
}