Čudna mreža

U jednom računarskom kabinetu potrebno je uspostaviti neobičnu računarsku mrežu. Potrebno je postaviti računare na \(n\) stolova, pri čemu na nekim stolovima mogu da stoje obični računari (njih imamo na raspolaganju u neograničenom broju), a na nekim posebni serveri (njih posebno moramo kupiti po ceni od \(c_s\) dinara). Neke stolove je moguće povezati direktno mrežnim kablovima, a neke nije. Cena uspostavljanja mrežnog kabla između bilo koja dva stola je \(c_k\) dinara. Napisati program koji određuje najmanju cenu koju je potrebno platiti tako da je svaki računar ili server ili je mrežnim kablom povezan sa bar jednim serverom (ne obavezno direktno).

Opis ulaza

Sa standardnog ulaza se u prvom redu unose brojevi \(c_s\) (\(0 \leq c_s \leq 1000\)) i \(c_k\) (\(0\leq c_k \leq 1000\)), razdvojeni razmakom. U narednom redu se unosi broj stolova \(n\) (\(2 \leq n \leq 50000\)) i \(m\) broj parova stolova između kojih je moguće postaviti mrežni kabl \(2 \leq m \leq \frac{n(n-1)}{2}\), razdvojeni razmakom. U narednih \(m\) redova unose se parovi brojeva između \(0\) i \(n-1\), razdvojenih razmakom koji određuju stolove između kojih je moguće postaviti kabl.

Opis izlaza

Primer

Ulaz

Izlaz

Rešenje

Opis glavnog rešenja

Ako je cena servera manja ili jednaka ceni jednog kabla, 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.

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.

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

#include <iostream>
#include <vector>

using namespace std;

class Network {
private:
  int number_of_computers;
  int number_of_cables;
  long long server_price;
  long long cable_price;
  vector<vector<int>> neighbours_list;

public:
  Network(int number_of_computers, int number_of_cables, long long server_price, long long cable_price) {
    this->number_of_computers = number_of_computers;
    this->number_of_cables = number_of_cables;
    this->server_price = server_price;
    this->cable_price = cable_price;
  }

  void add_edge_between_computers(int computer_1, int computer_2) {
    neighbours_list[computer_1].push_back(computer_2);
    neighbours_list[computer_2].push_back(computer_1);
  }

  int find_number_of_components() {
    // Za svaki racnuar cemo cuvati kojoj komponenti pripada. Komponenta 0 znaci da racunaru jos uvek nije dodeljena
    // nijedna komponenta
    vector<int> components(number_of_computers, 0);
    int component = 0;

    for (int computer = 0; computer < number_of_computers; computer++) {
      if (components[computer] == 0) {
        assign_component_to_computers(computer, components, ++component);
      }
    }
    return component;
  }

  void assign_component_to_computers(int computer, vector<int> &components, int component) {
    components[computer] = component;
    for (int neighbour : neighbours_list[computer]) {
      // Do sada neposeceni sused u komponenti
      if (components[neighbour] == 0) {
        assign_component_to_computers(computer, components, component);
      }
    }
  }

  int calculate_min_price() {
    if (server_price <= cable_price)
      return number_of_computers * server_price;
    else {
      int number_of_components = find_number_of_components();
      int number_of_servers = number_of_components;
      int number_of_regular_computers = number_of_computers - number_of_servers;
      return number_of_servers * server_price + number_of_regular_computers * cable_price;
    }
  }
};

int main() {
  ios_base::sync_with_stdio(false);

  int number_of_computers, number_of_cables;
  long long server_price, cable_price;
  cin >> server_price >> cable_price;
  cin >> number_of_computers >> number_of_cables;

  Network *N = new Network(number_of_computers, number_of_cables, server_price, cable_price);

  int computer_1, computer_2;
  for (int i = 0; i < number_of_cables; i++) {
    cin >> computer_1 >> computer_2;
    N->add_edge_between_computers(computer_1, computer_2);
  }

  std::cout << N->calculate_min_price() << "\n";

  delete N;
  return 0;
}