Cod sursa(job #884674)
#include <fstream>
#include <vector>
#define NMAX 200001
#define INF 10000000;
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
void citire();
void prim(int x);
struct muchie {int vf,cost;};
vector <muchie> C[NMAX];
int n,m,pre[NMAX],M[NMAX],Cmin[NMAX];
int main()
{
int i,s=0;
citire();
prim(1);
for(i=1;i<=n;i++) s+=Cmin[i];
fout<<s<<"\n"<<n-1<<"\n";
for(i=2;i<=n;i++)
fout<<i<<" "<<pre[i]<<"\n";
}
void citire()
{
int a,b,c,i;
muchie aux;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>a>>b>>c;
aux.vf=b;aux.cost=c;
C[a].push_back(aux);
aux.vf=a;
C[b].push_back(aux);
}
}
void prim(int x)
{
int i,vfmin,minim,j;
for(i=1;i<=n;i++) {Cmin[i]=INF;pre[i]=x;}
M[x]=1; Cmin[x]=0;
for(j=0;j<C[x].size();j++)
{
Cmin[C[x][j].vf]=C[x][j].cost;
pre[C[x][j].vf]=x;
}
for(i=1;i<n;i++)
{
minim=INF+1;
for(j=1;j<=n;j++)
if(Cmin[j]<minim&&M[j]==0)
{
minim=Cmin[j];
vfmin=j;
}
M[vfmin]=1;
for(j=0;j<C[vfmin].size();j++)
if(Cmin[C[vfmin][j].vf]>C[vfmin][j].cost&&M[C[vfmin][j].vf]==0)
{
Cmin[C[vfmin][j].vf]=C[vfmin][j].cost;
pre[C[vfmin][j].vf]=vfmin;
}
}
}