34ος ΠΔΠ B' Φάση: Ακριβό μου ντεπόζιτο (smalltank) - Λύση

Επεξήγηση εκφώνησης

Μας δίνεται ένας μη-κατευθυνόμενος γράφος \(G\) με \(V\) κορυφές και \(E\) ακμές με βάρη. Μας ζητείται να βρούμε το ελάχιστο βάρος \(w^\star\) ώστε να μπορούμε να πάμε από κάθε κορυφή \(u\) σε κάθε άλλη \(v\), διασχίζοντας μόνο ακμές \(e\) με βάρος \(w(e) \leq w^\star\).

Ακολουθεί η βασική παρατήρηση που θα χρησιμοποιήσουμε σε όλες τις παρακάτω λύσεις.

Παρατήρηση: Μπορούμε να πάμε από κάθε κορυφή \(u\) σε κάθε άλλη \(v\), διασχίζοντας μόνο ακμές \(e\) με βάρος \(w(e) \leq w\), αν και μόνο αν αφαιρώντας τις ακμές \(e\) με βάρος \(w(e) > w\), ο γράφος είναι συνδεδεμένος.

Για παράδειγμα, στον παρακάτω γράφο αν αφαιρέσουμε τις ακμές με βάρος \(> 8\), ο γράφος είναι συνδεδεμένος, άρα υπάρχει τρόπος να πάμε από κάθε ακμή σε κάθε άλλη με βάρη \(\leq 8\). Αν αφαιρέσουμε τις ακμές με βάρος \(> 5\), τότε ο γράφος δεν είναι συνδεδεμένος άρα δεν μπορούμε να πάμε από κάθε ακμή σε κάθε άλλη με βάρη \(\leq 5\).

Παραδείγματα συνδεδεμένου και μη-συνδεδεμένου γράφου

Ακολουθούν οι εξής λύσεις:

Brute force λύση: υλοποίηση της βασικής παρατήρησης
Λύση με δυαδική αναζήτηση: επιτάγχυνση της brute force λύσης (100%)
Λύση με disjoint sets: επιτάγχυνση της brute force λύσης (100%)
Αλγόριθμος Camerini: λύση με βέλτιστη πολυπλοκότητα (100%)

Brute force λύση

Η πρώτη λύση είναι να κάνουμε ακριβώς αυτό που λέει η βασική παρατήρηση: για κάθε \(w\) να αφαιρέσουμε τις ακμές με βάρος \(>w\) και να ελέγξουμε αν ο γράφος είναι συνδεδεμένος.

Ένας τρόπος να ελέγξουμε αν ο γράφος είναι συνδεδεμένος είναι κάνοντας αναζήτηση κατά βάθος (DFS). Ο τρόπος που δουλεύει η μη-αναδρομική DFS είναι διατηρώντας μία στοίβα \(\textit{st}\) και για κάθε κορυφή \(v\) το \(visit[v]\), που μας λέει αν έχουμε επισκεφθεί την κορυφή \(v\). Ξεκινάμε με την στοίβα να έχει μία οποιοδήποτε κορυφή. Έπειτα όσο η στοίβα δεν είναι άδεια, αφαιρεί την πάνω πάνω κορυφή και (αν δεν την έχουμε επισκεφθεί) προσθέτει τους γείτονές της στη στοίβα.

Ο παρακάτω κώδικας κάνει αυτό:

// Ελέγχουμε αν ο γράφος είναι συνδεδεμένος με 
// μη-αναδρομική DFS.
bool is_connected(long N) {
   std::fill(visited+1, visited+N+1, false);
   
   std::stack<long> st;
   long visited_count = 0;
   // Μπορούμε να ξεκινήσουμε από οποιαδήποτε κορυφή.
   st.push(1);
   while (!st.empty()) {
      long cur = st.top();
      st.pop();
      if (visited[cur]) continue;
      ++visited_count;
      visited[cur] = true;
      for (auto neigh : adj[cur]) {
         st.push(neigh);
      }
   }
   // Ο γράφος είναι συνδεδεμένος αν επισκεφτήκαμε 
   // όλους τους γείτονες.
   return visited_count == N;   
}

Έπειτα στο κυρίως τμήμα προσθέτουμε μία μία τις ακμές σε αύξουσα σειρά στον γράφο και ελέγχουμε αν ο γράφος είναι συνδεδεμένος:

   // Ταξινομούμε τις ακμές κατά αύξον βάρος.
   std::sort(edges.begin(), edges.end());
   
   long mx;
   for (auto [w, u, v] : edges) {
      // Προσθέτουμε την ακμή (u, v).
      adj[u].push_back(v);
      adj[v].push_back(u);
      if (is_connected(N)) {
         mx = w;
         break;
      }
   }

Ο έλεγχος για το αν ο γράφος είναι συνδεδεμένος θέλει \(\mathcal{O}(E + V)\) χρόνο και χρειάζεται να τον κάνουμε το πολύ μία φορά για κάθε ακμή. Άρα συνολικά ο αλγόριθμος χρειάζεται \(\mathcal{O}(E \cdot (V + E))\) χρόνο. Αυτό είναι αρκετό για να περάσει περίπου 14-16 από τα 21 testcases.

Ακολουθεί ολόκληρος ο κώδικας για αυτή τη λύση:

#include <algorithm>
#include <cstdio>
#include <stack>
#include <vector>
#include <tuple>

typedef std::tuple<long /* βάρος */, long /* 1η κορυφή */, long /* 2η κορυφή */> Edge;

const long MAXN = 10'000;

bool visited[MAXN + 1];
std::vector<std::vector<long>> adj; // Λίστα γειτνίασης.

// Ελέγχουμε αν ο γράφος είναι συνδεδεμένος με 
// μη-αναδρομική DFS.
bool is_connected(long N) {
   std::fill(visited+1, visited+N+1, false);
   
   std::stack<long> st;
   long visited_count = 0;
   // Μπορούμε να ξεκινήσουμε από οποιαδήποτε κορυφή.
   st.push(1);
   while (!st.empty()) {
      long cur = st.top();
      st.pop();
      if (visited[cur]) continue;
      ++visited_count;
      visited[cur] = true;
      for (auto neigh : adj[cur]) {
         st.push(neigh);
      }
   }
   // Ο γράφος είναι συνδεδεμένος αν επισκεφτήκαμε 
   // όλους τους γείτονες.
   return visited_count == N;   
}

int main() {
   long N, M;
   FILE *fi = fopen("smalltank.in", "r");
   fscanf(fi, "%ld%ld", &N, &M);
   adj.resize(N + 1);

   std::vector<Edge> edges;
   for (long i = 0; i < M; ++i) {
      long u, v, w;
      fscanf(fi, "%ld%ld%ld", &u, &v, &w);
      edges.push_back({ w, u, v });
   }
   fclose(fi);
   
   // Ταξινομούμε τις ακμές κατά αύξον βάρος.
   std::sort(edges.begin(), edges.end());
   
   long mx;
   for (auto [w, u, v] : edges) {
      // Προσθέτουμε την ακμή (u, v).
      adj[u].push_back(v);
      adj[v].push_back(u);
      if (is_connected(N)) {
         mx = w;
         break;
      }
   }
   
   FILE *fo = fopen("smalltank.out", "w");
   fprintf(fo, "%ld\n", mx);
   fclose(fo);
   
   return 0;
}

Λύση με δυαδική αναζήτηση

Στην προηγούμενη λύση, αν παρατηρήσουμε τις απαντήσεις για τις κλήσεις στην συνάρτηση is_connected, που γίνεται με αύξουσα σειρά στα βάρη, θα δούμε ότι οι απαντήσεις είναι false, false, false, ... , false, true, true, ..., true. Στο παραπάνω παράδειγμα, οι απαντήσεις είναι οι εξής:

Πώς αλλάζει ο γράφος από μη-συνδεδεμένος σε συνδεδεμένος όταν προσθέτουμε μία μία τις ακμές σε αύξουσα σειρά.

Εμείς θέλουμε να βρούμε το πρώτο σημείο που η συνάρτηση επιστρέφει true. Επομένως μπορούμε να χρησιμοποιήσουμε δυαδική αναζήτηση:

   long st = 0, en = M - 1;
   while (st < en) {
      long mn = (st + en) / 2;
      // Προσθέτουμε τις πρώτες mn ακμές.
      for (long i = 0; i <= mn; ++i) {
         auto [_, u, v] = edges[i];
         adj[u].push_back(v);
         adj[v].push_back(u);
      }
      if (is_connected(N)) {
         en = mn; // Απορρίπτουμε τα μεγαλύτερα βάρη.
      } else {
         st = mn + 1; // Απορρίπτουμε μικρότερα ή ίσα βάρη.
      }
      // Αδειάζουμε τον γράφο.
      adj = std::vector<std::vector<long>>(N + 1);
   }

Η δυαδική αναζήτηση θέλει \(\mathcal{O}(\log E) = \mathcal{O}(\log V)\) βήματα και κάθε ένα από αυτά τα βήματα θέλει \(\mathcal{O}(E + V)\) χρόνο. Επομένως, συνολικά θέλει \(\mathcal{O}((V+E) \cdot \log V)\) χρόνο, που είναι αρκετό για να περάσει όλα τα testcases. Μπορείτε να βρείτε εδώ ολόκληρο τον κώδικα.

Λύση με disjoint sets

Η λύση αυτή απαιτεί γνώσεις για disjoint sets. Μπορείτε να μάθετε περισσότερα εδώ ή εδώ.

Η δομή δεδομένων disjoint sets, μας επιτρέπει να διατηρήσουμε σύνολα κορυφών και να ενώσουμε (merge) ή να ελέγξουμε αν είναι ενωμένα (με την find_parent) σε amortised χρόνο \(\mathcal{O}(\log V)\)¹. Η υλοποίηση είναι η ακόλουθη.

int par[MAXN + 1];
int sz[MAXN + 1];

/* Αρχικοποίηση των disjoint sets. */
void init(long N) {
   for (int i = 1; i <= N; ++i) {
      par[i] = i;
      sz[i] = 1;
   }
}

/* Βρίσκουμε τον αντιπρόσωπο του συνόλου. */
long find_parent(long u) {
   if (u == par[u]) return u;
   return par[u] = find_parent(par[u]);
}

/* Ενώνουμε τα σύνολα που περιέχουν το 
   u και το v και επιστρέφουμε αν έγινε 
   καινούργια ένωση. */
bool merge(long u, long v) {
   long p_u = find_parent(u);
   long p_v = find_parent(v);
   
   if (p_u == p_v) return false;
   
   if (sz[p_u] < sz[p_v]) {
      par[p_u] = p_v;
   } else {
      par[p_v] = p_u;
      if (sz[p_u] == sz[p_v]) ++sz[p_u];
   }
   return true;
}

Ο κυρίως κώδικας παραμένει παρόμοιος:

   init(N);
   // Ταξινομούμε τις ακμές κατά αύξον βάρος.
   std::sort(edges.begin(), edges.end());
   
   long mx;
   for (auto [w, u, v] : edges) {
      if (merge(u, v)) {
         // Η τελευταία ενωση που κάνουμε είναι η 
         // μέγιστη ακμή (άρα και η απάντηση).
         mx = w;
      }
   }

Ο αλγόριθμος χρειάζεται \(\mathcal{O}(E \cdot \log V)\) χρόνο για την ταξινόμηση και \(\mathcal{O}(E \cdot \log V)\) συνολικά για τις ενώσεις. Η λύση αυτή περνάει όλα τα testcases. Μπορείτε να βρείτε εδώ ολόκληρο τον κώδικα.

Θεωρητική σημείωση: Ο αλγόριθμος αυτός είναι ίδιος με αυτόν του Kruskal για την εύρεση του ελάχιστου συνδετικού δένδρου (minimum spanning tree (mst)). Ισχύει ότι η απάντηση σε αυτό το πρόβλημα είναι η βαρύτερη ακμή σε ένα (οποιοδήποτε) mst. Επομένως θα μπορούσαμε να χρησιμοποιήσουμε οποιονδήποτε άλλον αλγόριθμο για την εύρεση του mst (πχ του Prim).

Γραμμικός αλγόριθμος

Το πρόβλημα αυτό έχει την ονομασία minimum bottleneck spanning tree και υπάρχει αλγορίθμος, γνωστός ως αλγόριθμος του Camerini, ο οποίος λύνει το πρόβλημα σε \(\mathcal{O}(E)\) χρόνο. Για τον διαγωνισμό, οι προηγούμενες λύσεις είναι εξίσου (ή και περισσότερο) αποδοτικές. Για όποιους ενδιαφέρονται, αναφέρουμε τα βήματα του αλγορίθμου:

Ο αλγόριθμος στηρίζεται ότι μπορούμε να βρούμε το μεσαίο όρο μίας ακολουθίας από \(N\) όρους σε \(\mathcal{O}(N)\) χρόνο. Ξεκινάμε βρίσκοντας την μεσαίου βάρους \(w_m\) ακμή. Προσθέτουμε όλες τις \(E/2\) ακμές με βάρος μικρότερο ή ίσο από αυτήν στον γράφο (σε \(\mathcal{O}(E)\) χρόνο). Αν ο γράφος είναι συνδεδεμένος ξέρουμε ότι η απάντηση είναι στις \(E/2\) μικρότερες, όποτε συνεχίζουμε αναδρομικά. Αν ο γράφος δεν είναι συνδεδεμένος, η απάντηση είναι στις \(E/2\) μεγαλύτερες, οπότε ενώνουμε τις κορυφές συνδεδεμένες με τις \(E/2\) μικρότερες ακμές και συνεχίζουμε αναδρομικά. Στις επόμενες αναδρομές θα έχουμε το πολύ \(E/4\) ακμές, μετά \(E/8\), κ.ο.κ.

Αν υλοποιήσουμε με προσοχή το κάθε βήμα ώστε να θέλει χρόνο γραμμικό προς το πλήθος των ακμών στον γράφο, τότε η συνολική πολυπλοκότητα είναι \(\mathcal{O}(E + E/2 + E/4 + E/8 + \ldots + 1) = \mathcal{O}(E)\) ². Μπορείτε να βρείτε εδώ ολόκληρο τον κώδικα.

Ο χρόνος είναι ακόμα καλύτερος, είναι \(\mathcal{O}(\alpha(V, E))\), όπου \(\alpha\) είναι η αντίστροφη συνάρτηση Ackermann, που παίρνει πολύ μικρές τιμές (δείτε πχ εδώ). Σε αυτή την περίπτωση, λόγω της ταξινόμησης δεν χρειάζόμαστε κάτι καλύτερο από \(\mathcal{O}(\log V)\). ↩
\(E + E/2 + E/4 + \ldots + 1 \leq E + E/2 + E/4 + \ldots = E \cdot (1 + 1/2 + 1/4 + 1/8 + \ldots) = 2 \cdot E\) ως το άθροισμα άπειρης γεωμετρικής προόδου με λόγο \(1/2\). ↩