Cod sursa(job #2942889)

Utilizator maria-marianita.cucos@s.unibuc.roCucos Marianita [email protected] Data 20 noiembrie 2022 11:54:47
Problema Paduri de multimi disjuncte Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 6.09 kb

//
//#include <iostream>
//#include <bits/stdc++.h>
//#define MAXX 4000
//
//using namespace std;
//
//ifstream f("retea2.in");
//ofstream g("retea2.out");
//
//int n, m;
//vector<pair<int, int>> blocuri, centrale;
//vector<double> distCentrala; // distanta fiecarui nod pana la cea mai apropiata centrala
//double distantaTotala; // distanta totala la final
//vector<bool> finalizat; // daca am decis pentru un nod care este distanta pe care o vom alege
//vector<double> distFinala; // distantele finale alese pentru a obtine APCM
//
//double dist(pair<int, int> p1, pair<int, int> p2) {
//    return sqrt((pow(p1.first - p2.first, 2)) + pow((p1.second - p2.second), 2));
//}
//
//int main() {
////    int n, m;
//    f >> n >> m;
////    blocuri.resize(m);
////    centrale.resize(n);
//    distCentrala.resize(m + 1, MAXX);
//    finalizat.resize(m + 1, false);
//    distFinala.resize(m + 1, MAXX);
//
////    vector<pair<int, int>> blocuri, centrale;
////    vector<double> distCentrala(m+1, MAXX); // distanta pana la cea mai apropiata centrala
////    double distantaTotala = 0; // distanta totala la final
////    vector<bool> finalizat(m+1, false); // daca am ales distanta finala pentru un nod
////    vector<double> distFinala(m+1, MAXX); // distantele finale alese pentru a obtine un APM
//
//    int x, y;
//    for (int i = 0; i < n; i++) {
//        f >> x >> y;
//        centrale.push_back( make_pair(x,y) );
//    }
//    for (int i = 0; i < m; i++) {
//        f >> x >> y;
//        blocuri.push_back( make_pair(x,y) );
//    }
//
//    // calculam distanta de la fiecare bloc la cea mai apropiata centrala de el
//    for (int i = 0; i < m; i++) {
//        for (int j = 0; j < n; j++)
//            distCentrala[i] = min(distCentrala[i], dist(blocuri[i], centrale[j]));
//        distFinala[i] = distCentrala[i];
//    }
//
//
//    for ( int i = 0; i < m; i++) {
//        double d = MAXX;
//        int ultim = -1;
//        // pentru fiecare nod care nu a fost finalizat il legam de cel mai apropiat nod deja finalizat
//        // initial avem distantele bloc-centrala, asa ca vom cauta si distantele bloc-bloc
//        for ( int j = 0; j < m; j++) {
//            if (!finalizat[j]) {
//                if (distFinala[j] < d) {  // caut cea mai mica distFinala
//                    d = distFinala[j];
//                    ultim = j;
//                }
//            }
//        }
//        // actualizam distanta totala
//        distantaTotala += d;
//        // Calculam distantele de la ultimul nod ales la celelalte noduri
//        // Modificam distFinala cu minimul dintre valorile existente si cele noi calculate astfel incat la urmatorul
//        // pas vom alege cea mai mica distanta dintre un nod nevizitat la unul vizitat
//        for ( int j = 0; j < m; j++)
//            distFinala[j] = min(distFinala[j], dist(blocuri[j], blocuri[ultim]));
//        finalizat[ultim] = true;
//    }
//    g << fixed << setprecision(6) << distantaTotala;
//    return 0;
//}
//
//
//

/* Tratam centralele ca pe un singur nod in graf, calculam distanta de la fiecare bloc(nod) la cea mai aporpiata
 * centrala. Folosind algoritmul lui Prim alegem cea mai mica distanta dintre nodul centralelor si nodurile blocurilor.
 */

#include <iostream>
#include <bits/stdc++.h>
#define INT_MAX 4000
using namespace std;

ifstream in("retea2.in");
ofstream out("retea2.out");


const int N = 2005;
const int M = 2005;


int n, m;
vector<pair<int, int>> centrale, blocuri;
vector<double> distantaCentrala; // distanta fiecarui nod pana la cea mai apropiata centrala
double finalDistance; // distanta totala la final
vector<bool> decided; // daca am decis pentru un nod care este distanta pe care o vom alege
vector<double> finalDistances; // distantele finale alese pentru a obtine APCM

double dist(pair<int, int> source, pair<int, int> dest) {
    return sqrt((pow(source.first - dest.first, 2)) + pow((source.second - dest.second), 2));

}

void read() {
    // alocare spatiu + citire
    in >> n >> m;
    distantaCentrala.resize(m + 1, INT_MAX);
    decided.resize(m + 1, false);
    finalDistances.resize(m + 1, INT_MAX);
    int x, y;
    for (int i = 0; i < n; i++) {
        in >> x >> y;
        centrale.push_back(make_pair(x, y));
    }
    for (int i = 0; i < m; i++) {
        in >> x >> y;
        blocuri.push_back(make_pair(x, y));
    }

    // calculam distanta de la fiecare bloc la cea mai apropiata centrala de el
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++)
            distantaCentrala[i] = min(distantaCentrala[i], dist(blocuri[i], centrale[j]));
        finalDistances[i] = distantaCentrala[i];
    }


}


int main() {
    read();

    for (int i = 0; i < blocuri.size(); i++) {
        double actDist = INT_MAX;
        int lastChosen = -1;
        // pentru fiecare nod care nu a fost ales il legam de cel mai apropiat nod deja ales
        // initial se considera ales nodul centralelor pentru ca finalDistances retine distantele minime
        // corespunzatoare centrala-bloc
        {
            for (int j = 0; j < blocuri.size(); j++) {
                if (!decided[j]) {
                    if (finalDistances[j] < actDist) {
                        actDist = finalDistances[j];
                        lastChosen = j;
                    }
                }
            }
        }
        // actualizam distanta finala
        finalDistance += actDist;
        // Calculam distantele de la ultimul nod ales la celelalte noduri.
        // Modificam finalDistances cu minimul dintre valorile existente si cele noi calculate astfel incat la urmatorul
        // pas vom alege cea mai mica distanta dintre un nod nevizitat la unul vizitat.
        for (int j = 0; j < blocuri.size(); j++)
            finalDistances[j] = min(finalDistances[j], dist(blocuri[j], blocuri[lastChosen]));
        decided[lastChosen] = true;
    }
    out << fixed << setprecision(6) << finalDistance;
    return 0;
}