Pagini recente » Cod sursa (job #652046) | Cod sursa (job #1806282) | Cod sursa (job #2081618)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie{int x,y,c;}v[400001];
int h[200001],t[200001],n,m,i,k,cost,sol[200001];
int comp(muchie a,muchie b)
{
return a.c<b.c;
}
int unionx(int x,int y)
{
int r1=x,r2=y,t1;
if(x==3&&y==7)
x=3;
while(t[r1]!=r1)
r1=t[r1];
while(t[r2]!=r2)
r2=t[r2];
while(t[x]!=r1)
{
t1=t[x];
t[x]=r1;
x=t1;
}
while(t[y]!=r2)
{
t1=t[y];
t[y]=r2;
y=t1;
}
if(r1==r2) return 0;
if(h[r1]<h[r2]) t[r1]=r2;
else t[r2]=r1;
if(h[r2]==h[r1]) h[r1]++;
return 1;
}
int main()
{
f>>n>>m;
for(i=1;i<=m;i++) f>>v[i].x>>v[i].y>>v[i].c;
for(i=1;i<=n;i++) {h[i]=1;t[i]=i;}
sort(v+1,v+m+1,comp);
k=0;i=1;
while(k<n-1)
{
if(unionx(v[i].x,v[i].y))
{
cost+=v[i].c;
sol[++k]=i;
}
i++;
}
g<<cost<<'\n'<<n-1<<'\n';
for(i=1;i<=k;i++) g<<v[sol[i]].x<<' '<<v[sol[i]].y<<'\n';
return 0;
}