Rețea de Orașe – Problemă Completă de Grafuri

Această problemă combină trei concepte fundamentale din teoria grafurilor: arbori de acoperire minimi, drumuri minime și componente conexe. Este o problemă complexă care testează înțelegerea profundă a algoritmilor pe grafuri și capacitatea de a combina soluții diferite pentru a rezolva cerințe multiple.

Descrierea Problemei

Considerăm o rețea de transport formată din N orașe conectate prin M drumuri bidirecționale. Fiecare drum are două atribute importante: o lungime (relevantă pentru distanțe) și un cost de întreținere (relevant pentru construcția rețelei).

Guvernul dorește să optimizeze rețeaua de transport urmând trei obiective distincte:

Construirea unei rețele de cost minim care conectează toate orașele
Respectarea unei constrângeri de grad maxim K pentru fiecare oraș
Calcularea distanțelor minime între orașe importante
Analiza robusteței rețelei prin eliminarea drumurilor scumpe

Cerințe Detaliate

1. Arbore de Acoperire Minim cu Constrângere de Grad

Primul obiectiv este să construim un arbore de acoperire (MST – Minimum Spanning Tree) cu cost total minim, dar cu o constrângere suplimentară: fiecare oraș poate avea cel mult K drumuri directe în rețeaua finală.

Această constrângere transformă problema clasică MST într-o variantă mai complexă care necesită algoritmi modificați.

2. Distanțe Minime – Algoritmul Dijkstra

Al doilea obiectiv este să calculăm distanța minimă între două orașe date folosind lungimile drumurilor. Aceasta este o aplicație clasică a algoritmului Dijkstra pe grafuri ponderate.

3. Componente Conexe – Disjoint Set Union

Al treilea obiectiv analizează robustețea rețelei prin eliminarea tuturor drumurilor cu cost de întreținere mai mare decât o valoare X. Trebuie să determinăm câte componente conexe rămân în rețeaua rezultată.

Algoritmi și Structuri de Date

Algoritmul Kruskal Modificat

Pentru prima cerință, folosim o variantă modificată a algoritmului Kruskal:

1. Sortăm toate muchiile după cost crescător
2. Iterăm prin muchiile sortate
3. Pentru fiecare muchie (u, v):
   - Verificăm dacă u și v sunt în componente diferite
   - Verificăm dacă grad[u] < K și grad[v] < K
   - Dacă ambele condiții sunt true:
     * Adăugăm muchia în MST
     * Unim componentele (DSU)
     * Incrementăm gradele

Complexitate: O(M log M) pentru sortare + O(M α(N)) pentru DSU

Algoritmul Dijkstra

Pentru distanțe minime, implementăm Dijkstra standard:

1. Inițializăm distanțe cu infinit
2. Setăm dist[sursa] = 0
3. Folosim un min-heap (nod, distanță)
4. Extragem nodul cu distanță minimă
5. Relaxăm muchiile adiacente
6. Repetăm până ajungem la destinație

Complexitate: O(M log N) folosind priority queue

Disjoint Set Union (DSU)

Pentru componente conexe, folosim DSU cu optimizări:

class DSU:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n

def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def unite(self, a, b): a, b = self.find(a), self.find(b) if a b: return False if self.rank[a] < self.rank[b]: a, b = b, a self.parent[b] = a if self.rank[a] self.rank[b]: self.rank[a] += 1 return True

Complexitate: O(M α(N)) unde α este funcția inversă Ackermann

Implementare în C++

Structuri de Date

struct Edge {
    int to, cost, length;
    bool operator<(const Edge& other) const {
        return cost > other.cost; // pentru min-heap
    }
};

class DSU {
private: vector parent, rank;
public: DSU { /* inițializare */ } int find(int x) { /* path compression */ } bool unite(int a, int b) { /* union by rank */ }
};

Funcția Principală

Funcția main() orchestrează cele trei etape:

int main() {
    // Citire date
    // 1. MST cu constrângere de grad
    // 2. Dijkstra pentru distanțe
    // 3. DSU pentru componente conexe
    // Afișare rezultate
}

Implementare în Python

Avantajele Python

Python oferă o sintaxă mai concisă și biblioteci integrate pentru structuri de date complexe:

import heapq  # pentru priority queue
from collections import defaultdict

Citire mai elegantă
N, M, K, Q, X = map(int, fin.readline().split())

DSU implementat ca o clasă
class DSU: def __init__(self, n): pass def find(self, x): pass def unite(self, a, b): pass

Analiza Complexității

Timp de Execuție

MST modificat: O(M log M) – dominat de sortare
Dijkstra: O(M log N) – eficient pentru grafuri rare
Componente conexe: O(M α(N)) – aproape liniar

Total: O(M log M + M log N) – acceptabil pentru constrângerile date

Memorie Utilizată

Graf: O(N + M) – listă de adiacență
DSU: O(N) – vectori parent și rank
Muchii: O(M) – pentru sortare și procesare

Total: O(N + M) – optim pentru N, M ≤ 10000

Testare și Validare

Caz de Test

Output:
185 # Cost MST cu grad ≤ 3
75 # Distanța minimă 1→6
2 # Componente conexe după eliminare cost > 50

Verificare Manuală

MST: Muchiile (1,2,20), (1,3,30), (2,4,60), (3,5,45), (4,6,70) = 225
Dijkstra: Drumul 1→2→4→6 = 10+25+40 = 75
Componente: Eliminăm muchiile cu cost > 50, rămân 2 componente

Extensii și Optimizări

Posibile Îmbunătățiri

Algoritmi alternativi: Prim modificat pentru MST cu constrângeri
Optimizări: Early termination în Dijkstra când ajungem la destinație
Paralelizare: Procesare paralelă a componentelor conexe

Aplicații Reale

Rețele de comunicare: Design de rețele cu constrângeri de grad
Transport urban: Planificare rute optime
Infrastructură: Analiza robusteței rețelelor critice

Concluzii

Această problemă demonstrează importanța combinării mai multor algoritmi de grafuri pentru a rezolva probleme complexe din lumea reală. Constrângerile suplimentare fac problema mai interesantă și mai apropiată de scenariile practice unde resursele sunt limitate.

Soluția prezentată este eficientă și scalabilă, putând gestiona rețele de dimensiuni moderate cu performanțe bune atât în C++ cât și în Python.

Lecții Învățate

Combinația de algoritmi: Problemele reale necesită adesea combinații de algoritmi
Constrângeri: Constrângerile pot transforma probleme standard în variante complexe
Flexibilitate: Alegerea limbajului potrivit poate simplifica implementarea
Testare: Validarea cu cazuri de test este esențială pentru corectitudine