Postavljanje računarske mreže - Rešenje

Problem modelujemo neusmerenim grafom kom su čvorovi stolovi, a grane postoje između svaka dva čvora (tj. stola) između kojih je moguće uspostaviti kabl.

Ako je cena servera manja ili jednaka ceni jednog kabla (iako ta pretpostavka nije realna), tada je najjeftinije na svaki sto postaviti po jedan server. Naime zamena svakog servera običnim računarom podrazumeva povezivanje tog računara sa nekim serverom pomoću jednog kabla, što povećava ukupnu cenu. Optimalna cena u tom slučaju je jednaka proizvodu broja računara \(n\) i cene servera \(c_s\).

U suprotnom je optimalno u svakoj komponenti povezanosti grafa. postaviti po jedan server i sve ostale stolove u toj komponenti popuniti običnim računarima povezanim sa tim serverom. Zaista, ako u nekoj komponenti ne bi postojao bar jedan server, onda računari u toj komponenti ne bi mogli biti povezani ni sa jednim serverom, što je suprotno uslovima zadatka. Ukoliko bi postojala bar dva servera u nekoj komponenti, cena ne bi bila optimalna. Naime jedan od ta dva servera bi se mogao zameniti običnim računarom koji bi se kablom povezao sa drugim serverom u toj komponenti, čime bi se umesto cene servera platila cena kabla koja je manja. Neka je \(k\) broj komponenata povezanosti. Potrebno je uspostaviti \(k\) servera (po jedan u svakoj komponenti), a ostale računare, njih \(n-k\) povezati kablom sa po jednim računarom. Zato je ukupna cena \(k\cdot c_s + (n-k)\cdot c_k\).

Broj komponenata povezanosti možemo jednostavno odrediti obilaskom grafa (na primer, rekurzivno implementiranim obilaskom u dubinu).

void dfs(const vector<vector<int>>& susedi,
         vector<int>& komponente,
         int cvor, int komponenta) {
  komponente[cvor] = komponenta;
  for (int sused : susedi[cvor])
    if (komponente[sused] == 0)
      dfs(susedi, komponente, sused, komponenta);
}

int broj_komponenata_povezanosti(const vector<vector<int>>& susedi,
                                 int broj_cvorova) {
  vector<int> komponente(broj_cvorova, 0);
  int komponenta = 0;
  for (int cvor = 0; cvor < broj_cvorova; cvor++)
    if (komponente[cvor] == 0)
      dfs(susedi, komponente, cvor, ++komponenta);
  return komponenta;
}

int main() {
  int broj_racunara, broj_kablova;
  long long cena_servera, cena_kabla;
  cin >> cena_servera >> cena_kabla;
  cin >> broj_racunara >> broj_kablova;
  vector<vector<int>> susedi(broj_racunara);
  for (int i = 0; i < broj_kablova; i++) {
    int racunar1, racunar2;
    cin >> racunar1 >> racunar2;
    susedi[racunar1].push_back(racunar2);
    susedi[racunar2].push_back(racunar1);
  }

  if (cena_servera <= cena_kabla)
    cout << broj_racunara * cena_servera << endl;
  else {
    int broj_komponenata = broj_komponenata_povezanosti(susedi, broj_racunara);
    int broj_servera = broj_komponenata;
    int broj_obicnih = broj_racunara - broj_servera;
    cout << broj_servera * cena_servera + broj_obicnih * cena_kabla << endl;
  }

  return 0;
}

#include <iostream>
#include <vector>

using namespace std;

void dfs(const vector<vector<int>>& susedi,
         vector<int>& komponente,
         int cvor, int komponenta) {
  komponente[cvor] = komponenta;
  for (int sused : susedi[cvor])
    if (komponente[sused] == 0)
      dfs(susedi, komponente, sused, komponenta);
}

int broj_komponenata_povezanosti(const vector<vector<int>>& susedi,
                                 int broj_cvorova) {
  vector<int> komponente(broj_cvorova, 0);
  int komponenta = 0;
  for (int cvor = 0; cvor < broj_cvorova; cvor++)
    if (komponente[cvor] == 0)
      dfs(susedi, komponente, cvor, ++komponenta);
  return komponenta;
}

int main() {
  int broj_racunara, broj_kablova;
  long long cena_servera, cena_kabla;
  cin >> cena_servera >> cena_kabla;
  cin >> broj_racunara >> broj_kablova;
  vector<vector<int>> susedi(broj_racunara);
  for (int i = 0; i < broj_kablova; i++) {
    int racunar1, racunar2;
    cin >> racunar1 >> racunar2;
    susedi[racunar1].push_back(racunar2);
    susedi[racunar2].push_back(racunar1);
  }

  if (cena_servera <= cena_kabla)
    cout << broj_racunara * cena_servera << endl;
  else {
    int broj_komponenata = broj_komponenata_povezanosti(susedi, broj_racunara);
    int broj_servera = broj_komponenata;
    int broj_obicnih = broj_racunara - broj_servera;
    cout << broj_servera * cena_servera + broj_obicnih * cena_kabla << endl;
  }

  return 0;
}