Pagini recente » Cod sursa (job #1211142) | Cod sursa (job #1286140) | Cod sursa (job #543792) | Cod sursa (job #967401) | Cod sursa (job #1941232)
#include <fstream>
#include <algorithm>
#include <string.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int a,b,c,n,m,i,tata[200001],nr,xx,yy,s,viz[200001];
struct du{
int x,y,cost;}muchii[400001];
int cmp(du u,du v){
if(u.cost<v.cost)
return 1;
return 0;
}
int main()
{
f>>n>>m;
for(i=1;i<=m;i++){
f>>a>>b>>c;
muchii[i].x=a;
muchii[i].y=b;
muchii[i].cost=c;
}
sort(muchii+1,muchii+m+1,cmp);
memset(tata,-1,sizeof(tata));
for(i=1;i<=m&&nr!=(n-1);i++){
xx=muchii[i].x;
yy=muchii[i].y;
while(tata[xx]>0)
xx=tata[xx];
while(tata[yy]>0)
yy=tata[yy];
if(xx!=yy){
viz[i]=1;
if(tata[xx]<tata[yy]){
tata[xx]+=tata[yy];
tata[yy]=xx;}
else{
tata[yy]+=tata[xx];
tata[xx]=yy;
}
s+=muchii[i].cost;
nr++;
}
}
g<<s<<'\n';
g<<n-1<<'\n';
for(i=1;i<=m;i++)
if(viz[i]==1)
g<<muchii[i].x<<" "<<muchii[i].y<<'\n';
return 0;
}