Cod sursă (job #362926)

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

using namespace std;

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

const int Nmax = 10001;

int N ;
int M;
int K;
int T[Nmax * 10];
short int H[Nmax * 10];
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 * 10], NewV[Nmax * 10],Last;

int sizeNew;int sizeOld;int Pos;

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]++;}
}
int BinarySearch(){
int pos = 1, step = (1<<20);

for(; step ; (step >>= 1))
if( pos + step <= sizeOld && V[pos + step].cost < V[sizeOld].cost)  pos += step;
return pos;
}

void Kruskal1(){

for(int i = 1; i <= N; ++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];

}
}
fout <<Cost<<'\n';

for(int i = 1; i <= sizeNew; i++) V[i] = NewV[i];

sizeOld = sizeNew;

}
void Kruskal2(){

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

//Pos = BinarySearch();

ok = false;  int Edge1 , Edge2; bool ok2 = false; int Ret;

NrEdges = 0; Cost = 0;

for(int i = 1; i <= N - 1; ++i){

if(Last.cost < V[i].cost && ok2 == false){
ok2 = true;
Edge1 = Find(Last.x);
Edge2 = Find(Last.y);

if(Edge1 != Edge2){

Reunite(Edge1, Edge2);
Cost += Last.cost;
NrEdges++;
ok = true;
Ret = i;
}
}

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

if(Edge1 != Edge2){
Reunite(Edge1, Edge2);

Cost += V[i].cost;

NrEdges++;

}else{ Pos = i; }
}
if(ok){

for(int i = Pos; i >= Ret; --i)
V[i] = V[i - 1];
V[Ret] = Last;

}

fout <<Cost<<'\n';
}

void Solve(){

Kruskal1();
for(int i = 1; i <= K; ++i) {
fin >> Last.x >> Last.y >> Last.cost;
Kruskal2();
}
}

int main(){

Read();
Solve();

return 0;
}