Cod sursă (job #757181)

#include<bits/stdc++.h>
using namespace std;
ifstream fin("zapada.in");
ofstream fout("zapada.out");

struct muchie{
    int i,j,cost;
};

int n , m , k, cnt, t[10003];
vector<pair<int,int>> v;
muchie x[110003];


void QuickSort(muchie v[], int st, int dr)
{
    if(st < dr)
    {
        //pivotul este inițial v[st]
        int m = (st + dr) / 2;

        swap(v[st],v[m]);
        int i = st , j = dr, d = 0;
        while(i < j)
        {
            if(v[i].cost > v[j].cost)
            {
                swap(v[i],v[j]);
                d = 1 - d;
            }
            else if(v[i].cost==v[j].cost){
                if(v[i].i>v[j].i){
                    swap(v[i],v[j]);
                    d = 1 - d;
                }
                else if(v[i].i==v[j].i){
                    if(v[i].j>v[j].j){
                        swap(v[i],v[j]);
                        d = 1 - d;
                    }
                }
            }
            i += d;
            j -= 1 - d;
        }
        QuickSort(v, st , i - 1);
        QuickSort(v, i + 1 , dr);
    }
}

void Insert(int m,int st,int dr){
    int poz=m;
    while(st<=dr){
        int mijl=(st+dr)/2;
        if(x[mijl].cost>x[m].cost){
            poz=mijl;
            dr=mijl-1;
        }

        else st=mijl+1;
    }
    muchie aux=x[m];
    for(int i=m;i>poz;i--){
        x[i]=x[i-1];
    }
    x[poz]=aux;
}

int main()
{
    fin >> n >> m >> k;
    for(int i = 0 ; i < m ; ++i)
        fin >> x[i].i >> x[i].j >> x[i].cost;

    //sortare tablou x[] după campul cost
    // ... de completat
    QuickSort(x,0,m-1);
    for(int l=0;l<k;l++){
        v.clear();

        //initializare reprezentanti
        for(int i =1 ; i <= n ; ++i)
            t[i] = i;
          //determinare APM
        int S = 0;
        for(int i = 0 ; i < m ; i ++)
            if(t[x[i].i] != t[x[i].j]) // extremitatile fac parte din subrabori diferiti
            {
                S += x[i].cost;
                v.push_back(make_pair(x[i].i,x[i].j));
                //reunim subarborii
                int ai = t[x[i].i], aj = t[x[i].j];
                for(int j =1 ; j <= n ; ++j)
                    if(t[j] == aj)
                        t[j] = ai;
            }
        fout << S << "\n";
        fin >> x[m].i >> x[m].j >> x[m].cost;
        Insert(m,0,m);
        m++;
    }
    Insert(m-1,0,m-1);
    //initializare reprezentanti
    for(int i =1 ; i <= n ; ++i)
        t[i] = i;
      //determinare APM
    int S = 0;
    v.clear();
    for(int i = 0 ; i < m ; i ++)
        if(t[x[i].i] != t[x[i].j]) // extremitatile fac parte din subrabori diferiti
        {
            S += x[i].cost;
            cnt++;
            v.push_back(make_pair(x[i].i,x[i].j));
            //reunim subarborii
            int ai = t[x[i].i], aj = t[x[i].j];
            for(int j =1 ; j <= n ; ++j)
                if(t[j] == aj)
                    t[j] = ai;
        }
    fout << S << "\n";
    fin.close();
    fout.close();

    return 0;
}