Pagini recente » Cod sursa (job #2978469) | Cod sursa (job #319987) | Cod sursa (job #1888158) | Cod sursa (job #987740) | Cod sursa (job #683048)
Cod sursa(job #683048)
#include<fstream.h>
#include<iostream.h>
ifstream f("apm.in");ofstream ou("apm.out");
int n,m,a[2000][3];
struct graf {int x,y,c;} g[2000],aj;
void citire()
{
int i=1;f>>n>>m;for(i=1;i<=m;i++) f>>g[i].x>>g[i].y>>g[i].c;
}
void sortare()
{
int i,j;
for(i=1;i<m;i++)
{
for(j=i+1;j<=m;j++)
{
if(g[i].c>g[j].c) {aj=g[i];g[i]=g[j];g[j]=aj;}
}
}
}
void pro()
{
int L[2000],i,j,k=0,s=0;
for(i=1;i<=n;i++) L[i]=i;
i=1;
while(k<n-1)
{
if(L[g[i].x]!=L[g[i].y])
{
L[g[i].x]=L[g[i].y];k++;s=s+g[i].c;a[i][1]=g[i].x;a[i][2]=g[i].y;
for(j=1;j<=m;j++) { if(L[j]==g[i].x) L[j]=g[i].y;}
}
i++;
}
ou<<s<<endl<<k<<endl;
for(i=1;i<=k;i++)
ou<<a[i][1]<<' '<<a[i][2]<<endl;
}
int main()
{
citire();sortare();pro();return 0;
}