Pagini recente »
Cod sursă (job #18837)
Cod sursă (job
#18837)
#include <fstream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 10001, M = 100001, inBuffSize = 1e6;
class Pmd{
int T[N], D[N];
public:
void init(int n){
for (int i = 1 ; i <= n ; i++){
T[i] = i;
D[i] = 1;
}
}
int tata(int x){
if (T[x] == x)
return x;
return T[x] = tata(T[x]);
}
bool merge(int x, int y){
x = tata(x);
y = tata(y);
if (x == y)
return false;
if (D[x] < D[y]){
T[x] = y;
D[y] += D[x];
} else {
T[y] = x;
D[x] += D[y];
}
return true;
}
};
struct Muchie{
int x, y, c;
Muchie(){
x = y = c = 0;
}
Muchie(int _x, int _y, int _c){
x = _x;
y = _y;
c = _c;
}
inline bool operator<(const Muchie& M) const {
return c < M.c;
}
};
Muchie edge[M];
int n, nrE, lastCost;
char inBuff[inBuffSize];
Pmd P;
ofstream out("zapada.out");
int add(Muchie A){
int poz;
for (poz = nrE ; poz && edge[poz].c > A.c ; poz--)
edge[poz + 1] = edge[poz];
edge[poz + 1] = A;
++nrE;
return poz + 1;
}
int evalApm(int mustHave){
int cost = 0, size = 0;
P.init(n);
for (int i = 1 ; i <= nrE ; i++)
if (P.merge(edge[i].x, edge[i].y)){
cost += edge[i].c;
edge[++size] = edge[i];
} else if (i == mustHave)
return lastCost;
nrE = n - 1;
return lastCost = cost;
}
int main(){
int times;
Muchie A;
FILE* in = fopen("zapada.in", "r");
setvbuf(in, inBuff, _IOFBF, inBuffSize);
fscanf(in, "%d %d %d", &n, &nrE, ×);
for (int i = 1 ; i <= nrE ; i++)
fscanf(in, "%d %d %d", &edge[i].x, &edge[i].y, &edge[i].c);
sort(edge + 1, edge + nrE + 1);
out << evalApm(1) << "\n";
while (times--){
fscanf(in, "%d %d %d", &A.x, &A.y, &A.c);
out << evalApm( add(A) ) << "\n";
}
return 0;
}