Cod sursă (job #363131)

#include <algorithm>
#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX = 1e4;
const int MMAX = 1e5;

struct Edge {
  short int from;
  short int to;
  int cost;

  bool operator< (Edge other) const {
    return cost < other.cost;
  }
};

short int n, k, no;
int m, maxx;
int res;
short int sef[1 + NMAX];

Edge v[1 + MMAX];

short int get_sef(short int el) {
  if(sef[el] == el)
    return sef[el];
  else {
    sef[el] = get_sef(sef[el]);
    return sef[el];
  }
}

void apm() {
  res = 0;
  no = 0;

  for(short int i = 1; i <= n; i++)
    sef[i] = i;

  for(int i = 1; i <= m && no <= n - 1; i++) {
    short int bx = get_sef(v[i].from);
    short int by = get_sef(v[i].to);

    if(bx != by) {
      sef[bx] = by;
      v[++no] = v[i];
      res += v[i].cost;
      maxx = max(maxx, v[i].cost);
    }
  }

  m = no;
  out << res << '\n';
}

int main()
{
  in >> n >> m >> k;
  for(int i = 1; i <= m; i++)
    in >> v[i].from >> v[i].to >> v[i].cost;
  sort(v + 1, v + m + 1);

  apm();

  for(short int w = 1; w <= k; w++) {
    m++;
    in >> v[m].from >> v[m].to >> v[m].cost;
    if(maxx < v[m].cost) {
      out << res << '\n';
      continue;
    }

    for(int i = m - 1; i >= 1; i--) {
      if(v[i + 1].cost < v[i].cost)
        swap(v[i], v[i + 1]);
      else
        break;
    }
    apm();
  }

  in.close();
  out.close();
  return 0;
}