Cod sursă (job #357027)

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 10005;
const int MMAX = 100005;

short Father[NMAX];
int bigger;
int P;
int countt;
int last  =0;

struct edge
{
    short x,y;
    int price;
}Edge[MMAX];
long long Answer = 0;
int N,M,K;
inline bool cmp( const edge &a , const edge &b)
{
    return a.price > b.price;
}
inline void ScanData()
{
    scanf("%d%d%d", &N ,&M , &K);

    for ( int i = 1; i <= M ; ++i)
    {
        scanf("%hu%hu%d", &Edge[i].x , &Edge[i].y  , &Edge[i].price);
    }
    sort(Edge+1,Edge+M+1, cmp);
    countt = M;

}
inline void Unite(int x, int y)
{
    Father[y] = x;
}

inline int Root(int Node)
{
    int R = Node;
    while(Father[R] > 0)
        R = Father[R];

    while(Father[Node] > 0)
    {
        Father[Node] = R;
        Node = R;
    }

    return Node;
}

inline void APM()
{
    memset(Father , 0 , sizeof Father);
    Answer = 0;
        bigger = 0;
    for ( int i = countt; i >= P ; --i)
    {
        int Node1 = Edge[i].x;
        int Node2 = Edge[i].y;
        int Price = Edge[i].price;

        int Root1 = Root(Node1);
        int Root2 = Root(Node2);

        if(Price == INT_MAX)
            {
                P = i;
                break;
            }

        if( Root1 != Root2)
        {
            Unite(Root1,Root2);
            Answer+=Price;
            if( Price > bigger)
                bigger = Price;
        }

        else Edge[i].price = INT_MAX;
    }

    printf("%lld\n" , Answer);
   // cout << "ultimule este " << P <<"\n";
}
int main()
{
    freopen("zapada.in" , "r" ,stdin);
   freopen("zapada.out" , "w", stdout);

   ScanData();

   APM();


   for ( int i = 1; i <= K ; ++i)
   {
       short a,b;
       int c;
       scanf("%hd%hd%d", &a,&b,&c);

       if( c > bigger)
        printf("%lld\n" , Answer);

       else
       {
           countt++;
           Edge[countt].x = a;
           Edge[countt].y = b;
           Edge[countt].price = c;

           sort(Edge+P+1 , Edge+M+1 , cmp);
           APM();

   /*for ( int i = 1; i <= countt ; ++i)
    cout << Edge[i].x <<" " << Edge[i].y <<" " << Edge[i].price <<"\n";
    cout <<"GAGATATATA\n";*/
       }
   }

   return 0;
}