Cod sursă (job #227136)

#include<fstream>
#include<vector>
#include<algorithm>

using namespace std;

ifstream fin("zapada.in");
ofstream fout("zapada.out");

const int Nmax = 10001;

int N ;
int M;
int K;
int T[Nmax * 10];
short int H[Nmax * 10];
int NrEdges;
long Cost;

bool ok = true;

struct Edge
{
    short int x;
    short int y;
    int cost;

    Edge() {}

    Edge(const int &x, const int&y, const int &cost)
    {
        this-> x = x;
        this -> y = y;
        this -> cost = cost;
    }
} V[Nmax * 10], NewV[Nmax * 10],Last;


int sizeNew;
int sizeOld;
int Pos;


struct cmp
{

    bool operator ()(const Edge &A, const Edge &B)const
    {
        return A.cost < B.cost;
    }
};

void Read()
{

    fin >> N >> M >>K;

    for(int i = 1; i <= M; ++i)
        fin >> V[i].x >> V[i].y >>V[i].cost;
    sizeOld =  M;
    sort(V + 1, V + 1 + sizeOld, cmp());
}

inline int Find(int X)
{

    int Node = X;

    for( ; Node != T[Node] ; Node = T[Node]);

    for( ; X != T[X];)
    {

        int Aux = T[X];
        T[X] = Node;
        X = Aux;
    }

    return Node;
}

inline void Reunite(const int &X, const int &Y)
{

    if(H[X] > H[Y])
    {
        T[Y] = X;
        H[X]++;
    }

    else
    {
        T[X] = Y;
        H[Y]++;
    }
}

int BinarySearch()
{
    int pos = 1, step = (1<<20);

    for(; step ; (step >>= 1))
        if( pos + step <= sizeOld && V[pos + step].cost < V[sizeOld].cost)  pos += step;

    return pos;
}

void Kruskal1()
{

    for(int i = 1; i <= N; ++i) T[i] = i, H[i] = 0;

    NrEdges = 0;
    Cost = 0;

    for(int i = 1; i <= sizeOld; ++i)
    {

        if(NrEdges == N - 1) break;


        int Edge1 = Find(V[i].x);
        int Edge2 = Find(V[i].y);

        if(Edge1 != Edge2)
        {

            Reunite(Edge1, Edge2);
            Cost += V[i].cost;
            NrEdges++;
            NewV[++sizeNew] = V[i];

        }
    }
    fout <<Cost<<'\n';

    for(int i = 1; i <= sizeNew; i++) V[i] = NewV[i];

    sizeOld = sizeNew;

}
void Kruskal2()
{

    for(int i = 1; i <= N; ++i) T[i] = i, H[i] = 0;

    //Pos = BinarySearch();

    ok = false;
    int Edge1 , Edge2;
    bool ok2 = false;
    int Ret;

    NrEdges = 0;
    Cost = 0;

    for(int i = 1; i <= N - 1; ++i)
    {

        if(Last.cost < V[i].cost && ok2 == false)
        {

            ok2 = true;
            Edge1 = Find(Last.x);
            Edge2 = Find(Last.y);

            if(Edge1 != Edge2)
            {

                Reunite(Edge1, Edge2);
                Cost += Last.cost;
                NrEdges++;
                ok = true;
                Ret = i;

            }
        }

        Edge1 = Find(V[i].x);
        Edge2 = Find(V[i].y);

        if(Edge1 != Edge2)
        {

            Reunite(Edge1, Edge2);
            Cost += V[i].cost;
            NrEdges++;

        }
        else
        {
            Pos = i;
        }



    }

    if(ok)
    {

        for(int i = Pos; i >= Ret; --i)
            V[i] = V[i - 1];
        V[Ret] = Last;
    }


    fout <<Cost<<'\n';
}

void Solve()
{

    Kruskal1();

    for(int i = 1; i <= K; ++i)
    {

        fin >> Last.x >> Last.y >> Last.cost;

        Kruskal2();
    }

}
int main()
{

    Read();

    Solve();

    return 0;
}