Cod sursă (job #291046)

#include <stdio.h>

#define NMAX 10001
#define MMAX 100000
#define NIL -1
#define INFINITY 1000000000

/******* Structuri disjuncte și rutine pentru algoritmul lui Kruskal ******/

typedef struct {
    short x, y;
    int c;
} edge;
edge e[MMAX];
int parent[NMAX]; // părintele în structura de mulțimi disjuncte
int rank[NMAX];   // înălțimea (aproximativă) în structura de mulțimi disjuncte

void sort(edge *e, int lo, int hi) {
    if (lo < hi) {
        int piv = e[hi].c, i = lo - 1;
        for (int j = lo; j < hi; j++) {
            if (e[j].c <= piv) {
                i++;
                edge tmp = e[i];
                e[i] = e[j];
                e[j] = tmp;
            }
        }
        i++;
        edge tmp = e[i];
        e[i] = e[hi];
        e[hi] = tmp;
        
        sort(e, lo, i - 1);
        sort(e, i + 1, hi);
    }
}

int find(int x) {
    int root = x;
    while (parent[root] != root) {
        root = parent[root];
    }
    while (x != root) {
        int tmp = parent[x];
        parent[x] = root;
        x = tmp;
    }
    return root;
}

void join(int x, int y) {
    x = find(x);
    y = find(y);
    if (x != y) {
        if (rank[x] < rank[y]) {
            parent[x] = y;
        } else if (rank[x] > rank[y]) {
            parent[y] = x;
        } else {
            parent[y] = x;
            rank[x]++;
        }
    }
}

/************** Stocarea și parcurgerea APM ***********************/

// Stocăm APM prin liste de adiacență, dar fără alocare dinamică
typedef struct {
    short other;
    int cost;
    int next;
} list;
list l[2 * NMAX];
int ad[NMAX]; // Începuturile listelor de adiacență

void init(int n) {
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        rank[i] = 0;
        ad[i] = NIL;
    }
}

// Adaugă muchia (x, y, c) la lista de adiacență a lui x
void addEdge(int slot, int x, int y, int c) {
    l[slot].other = y;
    l[slot].cost = c;
    l[slot].next = ad[x];
    ad[x] = slot;
}

// Șterge muchia (x,y) din lista de adiacență a lui x.
// Returnează indicele acelei muchii pentru a putea fi refolosit.
int deleteEdge(int x, int y) {
    int result;
    if (l[ad[x]].other == y) {
        result = ad[x];
        ad[x] = l[ad[x]].next;
    } else {
        int i = ad[x];
        while (l[l[i].next].other != y) {
            i = l[i].next;
        }
        result = l[i].next;
        l[i].next = l[l[i].next].next;
    }
    return result;
}

// Traversează arborele începând de la node.
// Dacă nodul target se află în subarbore, returnează 1 și setează
// u, v și cost ca fiind cea mai mare muchie de pe calea spre target.
// Altfel returnează 0.
// Folosește from ca să știe de unde a venit, ca să nu cicleze.
int traverse(int node, int from, int target, int *u, int *v, int *cost) {
    if (node == target) {
        *cost = 0;
        return 1;
    }
    for (int i = ad[node]; i != NIL; i = l[i].next) {
        if ((l[i].other != from) && traverse(l[i].other, node, target, u, v, cost)) {
            // Am găsit copilul care a dus spre target
            if (l[i].cost > *cost) {
                *cost = l[i].cost;
                *u = node;
                *v = l[i].other;
            }
            return 1;
        }
    }
    return 0;
}

void printEdges(int n) {
    for (int i = 1; i <= n; i++) {
        printf("ad[%d] = %d\n", i, ad[i]);
    }
    for (int i = 0; i < 2 * (n - 1); i++) {
        printf("edge %d other %d cost %d next %d\n", i, l[i].other, l[i].cost, l[i].next);
    }
}

int main() {
    int n, m, k;
    
    FILE *fin = fopen("zapada.in", "r");
    FILE *fout = fopen("zapada.out", "w");
    fscanf(fin, "%d %d %d", &n, &m, &k);
    for (int i = 0; i < m; i++) {
        fscanf(fin, "%hd %hd %d", &e[i].x, &e[i].y, &e[i].c);
    }
    
    // Rulează algoritmul lui Kruskal, calculează C_0 și un APM cu rădăcina 1.
    init(n);
    sort(e, 0, m - 1);
    int minCost = 0;
    for (int i = 0, joined = 0; joined < n - 1; i++) {
        if (find(e[i].x) != find(e[i].y)) {
            join(e[i].x, e[i].y);
            minCost += e[i].c;
            addEdge(2 * joined, e[i].x, e[i].y, e[i].c);
            addEdge(2 * joined + 1, e[i].y, e[i].x, e[i].c);
            joined++;
        }
    }
    // printEdges(n);
    fprintf(fout, "%d\n", minCost);
    
    // Acum inserează K muchii și actualizează arborele după fiecare
    while (k--) {
        int x, y, c, u, v, largestCost;
        fscanf(fin, "%d %d %d", &x, &y, &c);
        // Traversează arborele începând din x și găsește (u, v, max),
        // cea mai scumpă muchie de pe calea către y
        traverse(x, -1, y, &u, &v, &largestCost);
        // printf("Found %d %d %d\n", u, v, largestCost);
        if (largestCost > c) {
            int slot1 = deleteEdge(u, v), slot2 = deleteEdge(v, u);
            // printf("Freed slots %d %d\n", slot1, slot2);
            // printEdges(n);
            addEdge(slot1, x, y, c);
            addEdge(slot2, y, x, c);
            // printEdges(n);
            minCost += c - largestCost;
        }
        fprintf(fout, "%d\n", minCost);
    }
    
    fclose(fin);
    fclose(fout);
}