Pagini recente » Cod sursa (job #2005557) | Diferente pentru home intre reviziile 393 si 394 | Istoria paginii utilizator/barbudragos | probleme_oji_clasa_9 | Cod sursa (job #276091)
Cod sursa(job #276091)
#include<stdio.h>
#include<algorithm>
#include<vector>
#define MAXM 401001
using namespace std;
int i,j,n,m,cost;
int X[MAXM],Y[MAXM],C[MAXM],ind[MAXM],TATA[MAXM/2];
vector<int> sol;
bool cmp(const int &a,const int &b)
{
return C[a]<C[b];
}
int tata(int x)
{
int y=x;
while(y!=TATA[y])
y=TATA[y];
/*z=x;
while(z!=TATA[z])
{
aux=TATA[z];
TATA[z]=y;
z=aux;
}*/
return y;
}
int main(void)
{
freopen("apm.in","r",stdin);
freopen("apm.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
ind[i]=i;
scanf("%d%d%d",&X[i],&Y[i],&C[i]);
}
for(i=1;i<=n;i++)
TATA[i]=i;
sort(ind+1,ind+m+1,cmp);
int nr=0;
i=1;
int t1,t2;
while(nr<n&&i<=m)
{
j=ind[i];
t1=tata(X[j]);
t2=tata(Y[j]);
if(t1!=t2)
{
cost+=C[j];
TATA[t1] = t2;
sol.push_back(j);
nr++;
}
i++;
}
printf("%d\n%d\n",cost,nr);
for(i=0;i<nr;i++)
printf("%d %d\n",Y[sol[i]],X[sol[i]]);
return 0;
}