Pagini recente »
Cod sursă (job #18834)
Cod sursă (job
#18834)
#include <fstream>
#include <algorithm>
using namespace std;
const int N = 10001, M = 100001;
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, cost;
Pmd P;
ifstream in("zapada.in");
ofstream out("zapada.out");
void add(Muchie A){
int poz;
for (poz = nrE ; poz && edge[poz].c > A.c ; poz--)
edge[poz + 1] = edge[poz];
edge[poz + 1] = A;
}
int evalApm(){
int cost = 0;
P.init(n);
for (int i = 1 ; i <= nrE ; i++)
if (P.merge(edge[i].x, edge[i].y))
cost += edge[i].c;
return cost;
}
int main(){
int times;
Muchie A;
in >> n >> nrE >> times;
for (int i = 1 ; i <= nrE ; i++)
in >> edge[i].x >> edge[i].y >> edge[i].c;
sort(edge + 1, edge + nrE + 1);
out << evalApm() << "\n";
while (times--){
in >> A.x >> A.y >> A.c;
add(A);
out << evalApm() << "\n";
}
return 0;
}