Cod sursă (job #335193)

#include <stdio.h>
#include <stdlib.h>

#define MMAX 100000
#define NMAX 10000

typedef struct edge {
          short u, v;
          int c;
        } EDGE;

EDGE e[MMAX];
short tata[NMAX + 1];

int find(short v) {
  short r, u;

  u = v;
  while (tata[u] > 0) {
    u = tata[u];
  }

  r = u;
  u = v;
  while (u != r) {
    v = tata[u];
    tata[u] = r;
    u = v;
  }

  return r;
}

void join(short ra, short rb) {
  if (tata[ra] < tata[rb]) {
    tata[ra] = rb;
  } else {
      if (tata[rb] == tata[ra]) {
        tata[ra]--;
      }
      tata[rb] = ra;
  }
}


int kruskal(int n, int* m) {
  int i, j, cost;
  short ra, rb;

  for (i = 1; i <= n; i++) {
    tata[i] = -1;
  }

  cost = 0;
  i = 0; j = 0;
  while (i < n - 1) {
    ra = find(e[j].u);
    rb = find(e[j].v);

    if (ra != rb) {
      join(ra, rb);

      cost += e[j].c;
      if (i != j) {
        e[i] = e[j];
      }
      i++;
    }

    j++;
  }
  *m = i;

  return cost;
}

int partition(int l, int r, EDGE* a) {
  int i, j, x;
  EDGE tmp;

  x = a[r].c;
  for (i = l - 1, j = l; j <= r; j++) {
    if (a[j].c <= x) {
      i++;

      if (i < j) {
        tmp = a[i]; a[i] = a[j]; a[j] = tmp;
      }
    }
  }

  return i;
}

void quicksort(int l, int r, EDGE* a) {
  int pivot;

  if (l < r) {
    pivot = partition(l, r, a);

    if (pivot - 1 > l)
      quicksort(l, pivot - 1, a);

    if (pivot + 1 < r)
      quicksort(pivot + 1, r, a);
  }
}


int main() {
  FILE *fin, *fout;
  int n, m, k, i, j;
  EDGE tmp;

  fin = fopen("zapada.in", "r");
  fout = fopen("zapada.out", "w");

  fscanf(fin, "%d %d %d", &n, &m, &k);

  for (i = 0; i < m; i++) {
    fscanf(fin, "%hd %hd %d", &e[i].u, &e[i].v, &e[i].c);
  }
  quicksort(0, m - 1, e);

  fprintf(fout, "%d\n", kruskal(n, &m));

  for (i = 0; i < k; i++) {
    fscanf(fin, "%hd %hd %d", &e[m].u, &e[m].v, &e[m].c);

    j = m - 1; tmp = e[m];
    while (j >= 0 && tmp.c < e[j].c) {
      e[j + 1] = e[j];
      j--;
    }
    e[j + 1] = tmp;
    m++;

    fprintf(fout, "%d\n", kruskal(n, &m));
  }

  fclose(fin);
  fclose(fout);

  return 0;
}