Cod sursa(job #3373153)

Utilizator CorvinJudge0Corvin Judge CorvinJudge0 Data 6 noiembrie 2026 09:47:19
Problema Arbore partial de cost minim Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
ifstream fin("kruskal.in");
ofstream fout("kruskal.out");
typedef struct
{
    int x,y,c,u;
}muchie;
muchie a[5000],aux;
int n,v[101],m,s,i;
void citire ()
{
    int x,y,c,i;
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        a[i].x=x;
        a[i].y=y;
        a[i].c=c;
    }
}
void sorteaza ()
{
    int i,ok;
    do
    {
        ok=1;
        for (i=1;i<m;i++)
            if (a[i].c>a[i+1].c)
            {
                aux=a[i];
                a[i]=a[i+1];
                a[i+1]=aux;
                ok=0;
            }
    }while (ok==0);
}
void init ()
{
    int i;
    for (i=1;i<=n;i++)
        v[i]=i;
}
void afis ()
{
    int i;
    fout<<endl;
    for (i=1;i<=m;i++)
        fout<<a[i].x<<" "<<a[i].y<<" "<<a[i].c<<endl;
}
void inlocuieste (int x, int y)
{
    int i;
    for (i=1;i<=n;i++)
        if (v[i]==x)
            v[i]=y;
}
void kruskal ()
{
    int i=1;
    int k=0;
    while (k<n-1)
    {
        if (v[a[i].x]!=v[a[i].y])
        {
            a[i].u=1;
            s=s+a[i].c;
            k++;
            inlocuieste (v[a[i].x],v[a[i].y]);
        }
        i++;
    }
}
int main()
{
    citire ();
    sorteaza ();
    init ();
    kruskal ();
    fout<<s<<endl;
    for (i=1;i<=m;i++)
        if (a[i].u==1)
            fout<<a[i].x<<" "<<a[i].y<<endl;
    return 0;
}