Problema graf – OJI 2006, Clasa a 11-a

Enunțul problemei graf, de clasa a 11-a, dată în 2006 la OJI, se găsește pe PbInfo, .campion și InfoArena.

Rezumat graf

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 graf

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:

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

Sursă C++ graf

#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;
}

#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!

Problema graf – OJI 2006, Clasa a 11-a

Rezumat graf

Soluție graf

Sursă C++ graf

Îți place conținutul acestui site?

Similare

Introdu Comentariu Anulează răspunsul

Problema graf – OJI 2006, Clasa a 11-a

Rezumat graf

Soluție graf

Sursă C++ graf

Îți place conținutul acestui site?

Partajează asta:

Similare

Introdu Comentariu Anulează răspunsul