Pagini recente » Cod sursa (job #640638) | Cod sursa (job #2218112) | Cod sursa (job #857997) | Cod sursa (job #2420061) | Cod sursa (job #1164155)
#include <fstream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <queue>
#define in "retea2.in"
#define out "retea2.out"
#define Max_Size 2009
#define oo 100000000.00
typedef std :: pair < double, double > POINT;
typedef std :: pair < std :: pair < int, int> , double > MUCHIE;
std :: ifstream f(in);
std :: ofstream g(out);
std :: vector <MUCHIE > Graph;
int P[Max_Size], Rank[Max_Size];
struct cmp {
bool operator() (const MUCHIE &A, const MUCHIE &B) {
return (A.second < B.second);
};
};
class Retea {
public :
double Get_Distance(POINT, POINT);
double Get_Min_Cost(std :: vector < POINT >, std :: vector < double >);
std :: vector < double > Proc(std :: vector < POINT >, std :: vector < POINT>);
};
double Retea :: Get_Distance(POINT A, POINT B) {
double D = (A.first - B.first) * (A.first - B.first) + (A.second - B.second) * (A.second - B.second);
D = sqrt(D);
return D;
}
std :: vector < double > Retea :: Proc(std :: vector < POINT > Bloc, std :: vector < POINT > Centrala) {
std :: vector < double > D(Bloc.size());
for(int i = 0; i < D.size(); ++i) D[i] = Get_Distance(Bloc[i], Centrala[0]);
for(int i = 0; i < Bloc.size(); ++i)
for(int j = 1; j < Centrala.size(); ++j)
if(D[i] > Get_Distance(Centrala[j], Bloc[i])) D[i] = Get_Distance(Centrala[j], Bloc[i]);
return D;
}
double Retea :: Get_Min_Cost(std :: vector < POINT > Bloc, std :: vector < double > D) {
double ans = 0;
bool Viz[Bloc.size()][Bloc.size()];
for(int i = 0; i < Bloc.size(); ++i)
for(int j = 0; j < Bloc.size(); ++j) Viz[i][j] = 0;
std :: queue < int > Q;
Q.push(0); ans = D[0];
while(!Q.empty()) {
int nod = Q.front(), tnod; Q.pop();
double cost = oo; bool ok = 0;
for(int j = 0; j < Bloc.size(); ++j)
if(nod != j && !Viz[nod][j]) {
if(D[nod] + Get_Distance(Bloc[nod], Bloc[j]) < D[j]) {
if(D[nod] + Get_Distance(Bloc[nod], Bloc[j]) < cost) ok = 1, cost = D[nod] + Get_Distance(Bloc[nod], Bloc[j]), tnod = j;
}
else
if(D[nod] + Get_Distance(Bloc[nod], Bloc[j]) > D[j])
if(D[j] < cost) cost = D[j], tnod = j, ok = 1;
}
if(!Viz[nod][tnod] && !Viz[tnod][nod] && ok) {
Viz[nod][tnod] = Viz[tnod][nod] = 1;
ans += cost;
Q.push(tnod);
}
}
return ans;
}
int main() {
Retea obj;
int N, M;
f >> N >> M;
std :: vector < POINT > C(N), B(M), D(M + N);
std :: vector < double > Distance(M);
for(int i = 0; i < N; ++i) f >> C[i].first >> C[i].second, D[i] = C[i];
for(int j = 0; j < M; ++j) f >> B[j].first >> B[j].second, D[j + N] = B[j];
Distance = obj.Proc(B, C);
g << std :: fixed;
g << std :: setprecision(6) << obj.Get_Min_Cost(B, Distance) << '\n';
g.close();
return 0;
}