Enunțul problemei graf, de clasa a 11-a, dată în 2006 la OJI, se găsește pe InfoArena și PbInfo.
Rezumat
Se dă un graf neorientat conex, cu vârfurile etichetate de la $1$ la $n$, precum și două vârfuri distincte, notate cu $x$ și $y$. Trebuie să determinăm vârfurile care aparțin tuturor lanțurile optime (de lungime minimă) dintre $x$ și $y$.
Soluție
Notăm cu $lg(a, b)$ lungimea unui lanț optim între nodurile $a$ și $b$. Observăm că un nod $c$ aparține cel puțin unui lanț optim dintre $a$ și $b$ dacă și numai dacă $lg(a, b) = lg(a, c) + lg(c, a)$. De asemenea, dacă nu mai există alte noduri $d$, cu $lg(a, c) = lg(a, d)$, înseamnă că toate lanțurile optime de la $a$ la $b$ trec prin $c$.
Așadar, pentru a rezolva problema noastră, trebuie să căutăm toate nodurile ce îndeplinesc cele două condiții. Vom avea nevoie de niște parcurgeri în lățime pentru a calcula distanțele minime dintre noduri. O idee isteață este să facem doar două BFS-uri: Unul din $x$ și altul din $y$. Asta pentru că orice lanț de a cărui lungime avem nevoie are măcar o extremitate în $x$ sau în $y$. Ca să recapitulez:
- Facem BFS din $x$ și din $y$, reținând rezultatele în vectorii $\mathrm{dpX}$ și $\mathrm{dpY}$.
- Pentru fiecare nod $i$, dacă $\mathrm{dpX}[i] + \mathrm{dpY}[i] = \mathrm{dpX}[y]$, incrementăm $\mathrm{frq}[\mathrm{dpX}[i]]$ (numărul nodurilor ce se află pe un lanț elementar și cu distanța minimă până la $x$ egală cu $\mathrm{dpX}[i]$).
- Parcurgem din nou nodurile pentru a vedea care are $\mathrm{frq}[\mathrm{dpX}[i]] = 1$. Acestea sunt nodurile ce aparțin tuturor lanțurilor optime dintre $x$ și $y$. Le adăugăm la vectorul $sol$.
- Afișăm nodurile găsite la pasul anterior, precedate de numărul lor.
Sursă C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#include <queue> #include <vector> #include <fstream> #define DMAX 7510 using std::queue; using std::vector; std::ifstream fin("graf.in"); std::ofstream fout("graf.out"); int n, m; int x, y; vector<int> ad[DMAX]; // listele de adiacență int dpX[DMAX]; // pentru BFS-ul din x int dpY[DMAX]; // pentru BFS-ul din y int frq[DMAX]; // vectorul de frecvență vector<int> sol; // vectorul cu nodurile ce trebuie afișate /// Funcția pentru BFS din nodul start, /// cu stocarea lungimilor în vectorul dp void bfs(int start, int dp[]) { for (int i = 1; i <= n; i++) dp[i] = -1; queue<int> q; q.push(start); dp[start] = 0; while (!q.empty()) { int node = q.front(); q.pop(); for (int i = 0; i < ad[node].size(); i++) if (dp[ad[node][i]] == -1) { dp[ad[node][i]] = dp[node] + 1; q.push(ad[node][i]); } } } int main() { fin >> n >> m; fin >> x >> y; int a, b; for (int i = 0; i < m; i++) { fin >> a >> b; ad[a].push_back(b); ad[b].push_back(a); } bfs(x, dpX); bfs(y, dpY); for (int i = 1; i <= n; i++) if (dpX[i] + dpY[i] == dpX[y]) frq[dpX[i]]++; for (int i = 1; i <= n; i++) if (dpX[i] + dpY[i] == dpX[y] && frq[dpX[i]] == 1) sol.push_back(i); fout << sol.size() << '\n'; for (int i = 0; i < sol.size(); i++) fout << sol[i] << ' '; fout << '\n'; fout.close(); return 0; } |
Dacă ai vreo nedumerire cu privire la problema graf, lasă un comentariu și te voi ajuta 🙂
Îți place conținutul acestui site?
Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!