Cod sursa(job #1941232)

Utilizator cristibogdanPatrascu Cristian cristibogdan Data 27 martie 2017 08:23:35
Problema Arbore partial de cost minim Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#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;
}