Cod sursa(job #2351166)

Utilizator Horea_Mihai_SilaghiHorea Mihai Silaghi Horea_Mihai_Silaghi Data 22 februarie 2019 01:10:11
Problema Arbore partial de cost minim Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <algorithm>
#define maxn 400005
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int n,m,gr[maxn],x[maxn],y[maxn],c[maxn],ins[maxn],ans,ord[maxn];
bool cmp(int i,int j)
{
    return(c[i]<c[j]);
}
int findd(int i)
{
    if(gr[i]!=i)
        return findd(gr[i]);
    return i;
}
void reunire(int i, int j)
{
    gr[findd(i)]=findd(j);
}
int main()
{
    int i,j,l=0;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>x[i]>>y[i]>>c[i];
        ins[i]=i;
    }
    for(i=1;i<=n;i++)
        gr[i]=i;
    sort(ins+1,ins+m+1,cmp);
    for(i=1;i<=m;i++)
    {
        if(findd(x[ins[i]])!=findd(y[ins[i]]))
        {
            reunire(x[ins[i]],y[ins[i]]);
            ans+=c[ins[i]];
            l++;
            ord[l]=ins[i];
        }
    }
    cout<<ans<<'\n'<<n-1<<'\n';
    for(i=1;i<=n-1;i++)
        cout<<x[ord[i]]<<" "<<y[ord[i]]<<'\n';
    return 0;
}