Cod sursa(job #1916972)

Utilizator ImGeluGelu Ungur ImGelu Data 9 martie 2017 10:49:06
Problema Arbore partial de cost minim Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include<algorithm>
using namespace std;
ifstream cin ("apm.in");
ofstream cout ("apm.out");
struct bla
{
    int x,y,cost;
} t[400100],muchii[400010];
bool sortare (bla q,bla w)
{
    return q.cost<w.cost;
}
int n,m,flux,nr;
int tata[200010];
void read ()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>t[i].x>>t[i].y>>t[i].cost;
    sort(t+1,t+m+1,sortare);
}
int search_tata (int nod)
{
    if(tata[nod]!=nod)
        tata[nod]=search_tata(tata[nod]);
    return tata[nod];
}
void apm ()
{
    for(int i=1;i<=n;i++) tata[i]=i;
    for(int i=1;i<=m;i++)
    {
        int r1=search_tata(t[i].x),r2=search_tata(t[i].y);
        if(r1!=r2) tata[r1]=r2,flux+=t[i].cost,muchii[++nr]=t[i];
    }
}
void write ()
{
    cout<<flux<<"\n";
    cout<<nr<<"\n";
    for(int i=1;i<=nr;i++)
        cout<<muchii[i].x<<" "<<muchii[i].y<<"\n";
}
int main()
{
    read();
    apm();
    write();
    cin.close();
    cout.close();
    return 0;
}