Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1887
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1887
The Kunming-Singapore Railway
By Arthur Nascimento, Universidade de São Paulo 
Brazil
Timelimit: 10
The Kunming-Singapore Railway is a network of rail tracks (some already built, some under construction) connecting several Asian cities. The project started in 1900 with the goal to connect Kunming (China) to Singapore, through the British Empire. Afterwards, in 1918, the railway was connected to Thailand through rail track joining Bangkok and Singapore. In 2000, ASEAN (Association of Southeast Asian Nations) considered completing this railway system.
The project is scheduled for completion by 2020. Due to its importante for Southeast Asia integration, the contractors hired you to minimize the system maintenance cost. Given N cities that make up the Kunming-Singapore network, M initial rail tracks in the system and the Q tracks that will be built over time, you are required to compute the minimum cost do maintain the network connected after building each of these Q tracks. The system is initially connected if, for each pair of cities, there a set of tracks joining one to the other.
Input
The input is composed of many instances. The first line of the input contains an integer T which indicates the number of instances.
Each instance spans several lines. The first line has three space-separated integers, N, M, and Q (described above, 1 ≤ N, M, Q ≤ 3*104). The next M lines describe the initial rail tracks, and the next Q lines describe the tracks to be added over time. Each track is represented as three space-separated integers, a, b, and c (1 ≤ a, b ≤ N e 1 ≤ c ≤ 3*104), where a and b represent the cities that are endpoints of the track, and c is the maintenance cost.
Output
For each instance, print Q lines. The i-th line among these must have a single integer, the minimum maintenance cost after adding the i-th track.
| Input Sample | Output Sample |
|
1 |
18 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
typedef tuple < int, int, int, int> quadra;
const int MAXN = 30100;
const int BUCKET = 250;
vector < quadra> arestas, especiais;
vector<int> marca_antes, marca_depois;
int pai[MAXN], peso[MAXN], n, m, q, custo, last[MAXN], interacao,
pilha_pai[MAXN], pilha_peso[MAXN];
void zerar() {
for (int i = 1; i < = n; i++) pai[i] = i, peso[i] = 1;
}
void constroi_pilha() {
for (int i = 1; i < = n; i++) {
pilha_pai[i] = pai[i];
pilha_peso[i] = peso[i];
last[i] = interacao;
}
}
int find(int x) {
if (x == pai[x]) return x;
return pai[x] = find(pai[x]);
}
void join(int x, int y) {
x = find(x);
y = find(y);
if (peso[x] < peso[y]) swap(x, y);
peso[x] += peso[y];
pai[y] = x;
}
int find_pilha(int x) {
if (last[x] != interacao) {
last[x] = interacao;
pilha_pai[x] = pai[x];
pilha_peso[x] = peso[x];
}
if (x == pilha_pai[x]) return x;
return pilha_pai[x] = find_pilha(pilha_pai[x]);
}
void join_pilha(int x, int y) {
x = find_pilha(x);
y = find_pilha(y);
if (pilha_peso[x] < pilha_peso[y]) swap(x, y);
pilha_pai[y] = x;
pilha_peso[x] += pilha_peso[y];
}
int main() {
int TC;
scanf("%d", &TC);
while (TC--) {
arestas.clear();
marca_depois.clear();
marca_antes.clear();
interacao = 0;
scanf("%d %d %d", &n, &m, &q);
for (int i = 1; i < = m; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
arestas.push_back(make_tuple(w, u, v, -1));
marca_depois.push_back(0);
marca_antes.push_back(0);
}
for (int i = 0; i < q; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
arestas.push_back(make_tuple(w, u, v, i));
marca_depois.push_back(0);
marca_antes.push_back(0);
}
int tot_baldes = (q - 1) / BUCKET;
sort(arestas.begin(), arestas.end());
for (int balde_davez = 0; balde_davez < = tot_baldes; balde_davez++) {
zerar();
especiais.clear();
custo = 0;
int lo = balde_davez * BUCKET;
int hi = min((balde_davez + 1) * BUCKET - 1, q - 1);
for (int i = 0; i < arestas.size(); i++)
marca_antes[i] = marca_depois[i] = 0;
for (int i = 0; i < arestas.size(); i++) {
int u = get<1>(arestas[i]), v = get<2>(arestas[i]),
t = get<3>(arestas[i]), w = get<0>(arestas[i]);
if (t >= lo) continue;
if (find(u) != find(v)) {
join(u, v);
marca_antes[i] = 1;
}
}
zerar();
for (int i = 0; i < arestas.size(); i++) {
int u = get<1>(arestas[i]), v = get<2>(arestas[i]),
t = get<3>(arestas[i]), w = get<0>(arestas[i]);
if (t > hi) continue;
if (find(u) != find(v)) {
join(u, v);
marca_depois[i] = 1;
}
}
zerar();
for (int i = 0; i < arestas.size(); i++) {
int u = get<1>(arestas[i]), v = get<2>(arestas[i]),
t = get<3>(arestas[i]), w = get<0>(arestas[i]);
if (t > hi) continue;
if (lo < = t && t <= hi) {
especiais.push_back(arestas[i]);
}
if (marca_antes[i] == 0) continue;
if (marca_depois[i] == 1) {
// printf("Sempre U %d V %d W %d\n",u,v,w);
join(u, v);
custo += w;
} else {
especiais.push_back(arestas[i]);
}
}
constroi_pilha();
for (int tempo = lo; tempo < = hi; tempo++) {
int delta = 0;
interacao++;
for (int i = 0; i < especiais.size(); i++) {
int u = get<1>(especiais[i]), v = get<2>(especiais[i]),
t = get<3>(especiais[i]), w = get<0>(especiais[i]);
if (t > tempo) continue;
if (find_pilha(u) != find_pilha(v)) {
// printf("U %d V %d W %d\n",u,v,w);
join_pilha(u, v);
delta += w;
}
}
printf("%d\n", custo + delta);
}
}
}
return 0;
}
Input
4 3 5
1 2 5
2 3 6
3 4 7
1 4 8
1 2 4
2 4 5
3 4 5
1 4 6
Output
17
15
14
14