Cerința

Se dă mulțimea V a arcelor unui graf orientat cu n vârfuri.
Să se determine drumul simplu de lungime maximă cu extremitatea inițială în vârful p din graf. Un drum simplu parcurge o singură dată un arc de pe traseul descris de drum în graf.

Date de intrare

Fișierul de intrare dslm.in conține pe prima linie numerele n și p, iar pe fiecare din următoarele linii, câte două numere a b reprezentând câte un arc (a,b) din V.

Date de ieșire

Fișierul de ieșire dslm.out va conține pe prima linie cel mai mic drum în sens lexicografic dintre drumurile simple de lungime maximă cu extremitatea inițială în nodul p; vârfurile din drum sunt separate prin câte un singur spațiu.

Restricții și precizări

1 ≤ n ≤ 20
1 ≤ a , b ≤n
1 ≤ p ≤ n
mulțimea V are cel mult 30 de elemente
pentru fiecare test există soluție
dacă există mai multe soluții, atunci se va scrie în fișier cel mai mic drum în sens lexicografic dintre soluțiile obținute

Exemplu

dslm.in

dslm.out

2 3 1 4 5 7 5

Explicație

Graful conține un singur drum simplu de lungime maximă cu extremitatea inițială în vârful p=2, D=[2,3,1,4,5,7,5]

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema DSLM:

#include <fstream>
using namespace std;
ifstream f("dslm.in");
ofstream g("dslm.out");

int a[21][21],n,p, d[100], dmax[100],lgmax;

void citire()
{
    int i,x,y;
    f>>n>>p;
    while(f>>x>>y)
        a[x][y]=1;
}
void copie(int lg)
{
    lgmax=lg;
    for(int i=1; i<=lg; i++) dmax[i]=d[i];
}

void scrie_drum()
{
    for(int i=1; i<=lgmax; i++)
        g<<dmax[i]<<" ";
    g<<endl;
}

void dfs(int x, int lg)
{
    d[lg]=x;
    int ex_s=0, y;
    for(y=1; y<=n; y++)
        if(a[x][y])
        {
            a[x][y]=0;
            ex_s=1;
            dfs(y,lg+1);
            a[x][y]=1;
        }
    if(ex_s==0 && lg>lgmax)
        copie(lg);
}

int main()
{
    citire();
    dfs(p,1);
    scrie_drum();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1551 DSLM

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1551 DSLM de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1551 DSLM