Cod sursă (job #363140)

#include <algorithm>
#include <iostream>
#include <memory.h>
#include <fstream>

using namespace std;

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

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

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 pos = DIM - 1;
int m, maxx;
int res;
short int sef[1 + NMAX];
char buff[DIM];

Edge v[1 + MMAX];

short int get_sef(short int el) {
  if(sef[el] == 0)
    return 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;
  memset(sef, 0, sizeof(sef));

  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 read() {
  int x = 0;
  while(!isdigit(buff[pos])) {
    if(++pos == DIM) {
      in.read(buff, DIM);
      pos = 0;
    }
  }

  while(isdigit(buff[pos])) {
    x = x * 10 + (buff[pos] -'0');
    if(++pos == DIM) {
      in.read(buff, DIM);
      pos = 0;
    }
  }

  return x;
}

int main()
{
  //in >> n >> m >> k;
  n = read();
  m = read();
  k = read();

  for(int i = 1; i <= m; i++) {
    //in >> v[i].from >> v[i].to >> v[i].cost;
    v[i].from = read();
    v[i].to = read();
    v[i].cost = read();
  }
  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;
    v[m].from = read();
    v[m].to = read();
    v[m].cost = read();
    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;
}