Cod sursă (job #362873)

#include<fstream>
#include<vector>
#include<algorithm>

using namespace std;

ifstream fin("zapada.in");
ofstream fout("zapada.out");

const int Nmax = 100001;

int N ;
int M;
int K;
int T[Nmax];
short int H[Nmax];
int NrEdges;
long Cost;

bool ok = true;

struct Edge{
short int x; short int y; int cost;

Edge(){}

Edge(const int &x, const int&y, const int &cost){
this-> x = x; this -> y = y; this -> cost = cost;

}
}V[Nmax], NewV[Nmax];

int sizeNew; int sizeOld;

struct cmp{

bool operator ()(const Edge &A, const Edge &B)const{
return A.cost < B.cost;
}
};

void Read(){

fin >> N >> M >> K;

for(int i = 1; i <= M; ++i)
fin >> V[i].x >> V[i].y >>V[i].cost;
sizeOld =  M;
sort(V + 1, V + 1 + sizeOld, cmp());
}

inline int Find(int X){

int Node = X;

for( ; Node != T[Node] ; Node = T[Node]);

for( ; X != T[X];){
int Aux = T[X];
T[X] = Node;
X = Aux;
}

return Node;
}

inline void Reunite(const int &X, const int &Y){

if(H[X] > H[Y]) {T[Y] = X; H[X]++;}
else{ T[X] = Y; H[Y]++;}
}

void Kruskal(){

//sort(V + 1, V + 1 + sizeOld, cmp());

int Pos = sizeOld;
if( ok == false)
for(int i = 1; i <= sizeOld; ++i)
if(V[sizeOld].cost < V[i].cost){
Pos = i - 1;
break;
}

for(int i = 1; i <= sizeOld; ++i) T[i] = i, H[i] = 0;

NrEdges = 0; Cost = 0;

for(int i = 1; i <= sizeOld; ++i){

if(NrEdges == N - 1) break;

int Edge1 = Find(V[i].x);
int Edge2 = Find(V[i].y);

if(Edge1 != Edge2){

Reunite(Edge1, Edge2);
Cost += V[i].cost;
NrEdges++;
NewV[++sizeNew] = V[i];

}

if(NrEdges == N - 1) break;

if(i == Pos && ok == false){

Edge1 = Find(V[sizeOld].x);

Edge2 = Find(V[sizeOld].y);

if(Edge1 != Edge2)
    {
Reunite(Edge1, Edge2);
Cost += V[sizeOld].cost;
NrEdges++;
NewV[++sizeNew] = V[sizeOld];
    }

}
}
fout <<Cost<<'\n';ok = false;
for(int i = 1; i <= sizeNew; i++) V[i] = NewV[i];

sizeOld = sizeNew;
sizeNew = 0;
}

void Solve(){

Kruskal();
for(int i = 1; i <= K; ++i) {
++sizeOld;
fin >> V[sizeOld].x >> V[sizeOld].y >> V[sizeOld].cost;
Kruskal();
}
}

int main(){
Read();

Solve();

return 0;
}