Problema Graf – OJI 2006, Clasa a 11-a

Problema Graf – OJI 2006, Clasa a 11-a

Rezumat

Se dă un graf neorientat conex, cu vârfurile etichetate de la 11 la nn precum și două vârfuri distincte, notate cu xx și yy Trebuie să determinăm vârfurile care aparțin tuturor lanțurilor optime (de lungime minimă) dintre xx și yy

Soluție

Notăm cu d(a,b)d(a, b) lungimea unui lanț optim între nodurile aa și bb Observăm că un nod cc aparține cel puțin unui lanț optim dintre aa și bb dacă și numai dacă d(a,b)=d(a,c)+d(c,a)d(a, b) = d(a, c) + d(c, a) Mai mult, dacă nu mai există alte astfel de noduri cc' cu d(a,c)=d(a,c)d(a, c) = d(a, c') înseamnă că toate lanțurile optime de la aa la bb trec prin cc

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 xx și altul din yy Asta pentru că orice lanț de a cărui lungime avem nevoie are măcar o extremitate în xx sau în yy Ca să recapitulez:

  1. Facem BFS din xx și din yy reținând rezultatele în vectorii dpX și dpY.
  2. Pentru fiecare nod ii dacă dpX[i] + dpY[i] = dpX[y], incrementăm dpX[i] (numărul nodurilor ce se află pe un lanț optim și care sunt situate la distanța dpX[i] de xx
  3. Parcurgem din nou nodurile pentru a vedea care au frq[dpX[i]] = 1. Acestea sunt nodurile ce aparțin tuturor lanțurilor optime dintre xx și yy Le adăugăm la vectorul ans.
  4. Afișăm nodurile găsite la pasul anterior, precedate de numărul lor.

Sursă C++

Problema Graf
#include <bits/stdc++.h>
using namespace std;
ifstream fin("graf.in");
ofstream fout("graf.out");
int main() {
int n, m, x, y; fin >> n >> m >> x >> y;
vector<vector<int>> ad(n + 1);
for (int i = 0; i < m; i++) {
int x, y; fin >> x >> y;
ad[x].push_back(y);
ad[y].push_back(x);
}
function<void(int, vector<int>&)> bfs = [&](int src, vector<int>& dp) {
fill(dp.begin(), dp.end(), -1);
dp[src] = 0;
queue<int> q; q.push(src);
while (!q.empty()) {
int node = q.front(); q.pop();
for (int nghb : ad[node])
if (dp[nghb] == -1) {
dp[nghb] = dp[node] + 1;
q.push(nghb);
}
}
};
vector<int> dpX(n + 1); bfs(x, dpX);
vector<int> dpY(n + 1); bfs(y, dpY);
vector<int> frq(n);
for (int i = 1; i <= n; i++)
if (dpX[i] + dpY[i] == dpX[y])
frq[dpX[i]]++;
vector<int> ans;
for (int i = 1; i <= n; i++)
if (dpX[i] + dpY[i] == dpX[y] && frq[dpX[i]] == 1)
ans.push_back(i);
fout << ans.size() << '\n';
for (int node : ans)
fout << node << ' ';
fout << '\n';
return 0;
}

Dacă ai vreo nedumerire cu privire la problema Graf, lasă un comentariu și te voi ajuta

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii