199 Graf

[ditzone]

Aici puteţi discuta despre problema Graf.

[•peanutz]

testul din enunt:

Cod:

6 7 1 4
1 2
1 3
1 6
2 5
3 5
5 6
5 4

cu raspunsul

Cod:

3
1 4 5

Imi poate explica cineva cum ajungi din 1 in 4 trecand prin 5? Adica nu ar mai trebui sa treaca prin 2 sau prin 3(intre 1 si 5 nu exista legatura directa).

[•crawler]

lanturile optime intre 1 si 4 sunt:
  - 1 2 5 4
  - 1 3 5 4
  - 1 6 5 4

[•peanutz]

Scuze, am interpretat gresit   

Chiar si asa, solutia mea care afiseaza toate varfurile lanturilor optime(chiar daca nu sunt comune), ia 50

[•toni2007]

cred ca testele la aceasta problema nu sunt foarte bune...

Am luat 90 cu o sursa cu bulaneli: aveam un hibrid: daca n<=200 faceam un Bellmanford pt fiecare nod i (dinspre x spre celelalte, mai putin nodul i) si verificam daca minimul in acest caz este mai mare decat minimul normal (cu toate nodurile), iar pt n>200 faceam doua Bellmanforduri din x si respectiv din y si vedeam daca

Cod:

distx[i] + disty[i] == distx[y] 

  si atunci adaugam nodul la solutie...

cred ca trebuie refacute testele 6-9

[•raica_cristi]

eu inebunesc deja cu problema asta ... oricum as modifica-o tot 80 iau ... 
daca imi puteti spune ce gresesc aici v-as fi recunoscator

Cod:

#include<stdio.h>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>

using namespace std;

#define dim 8000
#define pb push_back

vector < int > v [ dim*3 ] ;
int plm[dim];
queue < int > q;
int n,m,n1,n2;
int  dst [ dim ] ,f[dim],t[dim];
bitset <dim> nr;
void read()
{
    int x,y;
    scanf("%d %d %d %d\n",&n,&m,&n1,&n2);
    for(int i=1 ;i<=m;i++)
    {
        scanf("%d %d\n",&x,&y);
        v[x].pb(y);
       v[y].pb(x);
    }
}
void solve()
{
    int x,i;
    dst[ n1 ] =1;
    for(q.push(n1) ; !q.empty() ; q.pop())
    {
        x = q.front ();
        for(int i=0 ; i<v[x].size() ; i++)
        {
            if (dst [ v[ x ] [ i ]] == 0 )
            {
                dst [ v[x][i] ] = dst[ x ] +1;
                f[ v[x][i]] = f[ x ] ;
                q.push ( v[x][i] ) ;
                t[ v[x][i] ] = x;
            }
            else
            if( dst[v[ x ] [ i ]] == dst[ x ]+1  )
            f[ v[x][i] ] ++;
        }
      
    }
    int x2=n2,l=0;
   while ( x2 )
    {
       if ( f[x2] == f[t[x2] ] && t[x2] !=0 )
            dst[ ++l ] =t[x2];
        x2= t [ x2 ] ;
    }
    dst[ ++l ] = n2 ;
    sort ( dst + 1 , dst + l + 1 );
    printf("%d\n",l);
    for(int i=1 ;i<=l;i++)
    printf("%d " ,dst [ i ]);
}


int main ()
{
    freopen("graf.in","r",stdin);
    freopen("graf.out","w",stdout);
    read();
    solve();
    return 0;
    
}

[•cdascalu]

           Salut,

Iau 90 pct cu tle pe testul 4.
Am luat testele de la oji si raspunsul la testul 3 este:

Cod:

2
58 59 60

Nu ar trebui sa fie pe prima linie 3???(eu asa am inteles din enunt).

[•blustudio]

Ar putea sa imi spuna cineva ce e gresit in abordarea urmatoare?

1. Parcurg in latime graful incepand cu nodul X
2. Daca intalnesc un nod care imbunatateste distanta pana la unul din vecinii sai V, atunci golesc lista de tati a lui V.
3. Daca acelasi nod da un cost egal cu costul pt a ajunge in vecinul V atunci il adaug in lista de tati a lui V.
4. Dupa parcurgere pentru fiecare tata T a lui Y parcurg recursiv pana la X astfel ca maresc numarul de aparitii al fiecarui nod intalnit si apoi merg la tatal cu numarul (aparitii - 1).
5. Pentru fiecare nod care are numarul de aparitii egal cu numarul de aparitii al lui X il adaug intr-un heap.
6. Tiparesc heap-ul.

[•bratiefanut]

desi la tag este parcurgere in latime, se poate face si cu roy-floyd? sau pt ca este O(n*n*n) o sa iasa din timp?

[•visanr]

desi la tag este parcurgere in latime, se poate face si cu roy-floyd? sau pt ca este O(n*n*n) o sa iasa din timp?

Nu poti roy-floyd, e prea mare complexitatea. Ca sa iti intre cum zici tu, ar trebui ca N sa fie ~ 100, dar aici e 7500.

[•bratiefanut]

deci pentru teste mici ar merge, nu?

[•visanr]

deci pentru teste mici ar merge, nu?

Pai din cate vad, in solutia mea folosesc distante minime intre noduri, deci da, ar merge.

[•stardust]

Pai pentru 50% din teste N<=200. Deci s-ar putea sa iei pana la 50 de puncte cred.

[•bratiefanut]

am incercat roy floyd-ul.. merge dar eu trebuie sa afisez nodurile comune tuturor lanturilor optime, nu doar lantul optim.. trebuie modificat putin algoritmul, si iese din timp de pe la testu 4 incolo, deci poti lua maxim 40

[•cont_teste]

oricum problema asta iese foarte usor cu BFS .

[•witsel]

imi poate spune ce e gresit in problema???
Deci prima oara fac parcurgerea in latime de la nodul X la nodul Y. Dupa care merg de la nodul Y si pentru fiecare vecin cu costul minim(

Cod:

L[now]==L[p->vecin]+1

, unde L[now] repr lungimea minima de la nodul X pana la nodul curect si L[p->vecin] lungimea de la nodul X pana la vecinul nodului curent(now) si pt fiecare vecin care indeplineste conditiile astea maresc aparitia nodului curent in lant si nr cu 1(nr reprezinta numarul de lanturi optime)). La sfarsit egalez numarul de aparitii al nodului X si Y cu nr si fac maximul din vectorul de aparitii si afisez toate nodurile egale cu acel maxim.

P.S. : de ce la testul al doilea sunt doua drumuri intre 1 si 3 cand ar trb sa fie doar unul???

Cod:

#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("graf.in");
ofstream fout("graf.out");
const int NMAX=100005,MMAX=1000005,inf=2000000;
int N,M,S,L[MMAX],now,poz[NMAX],ap[NMAX],nr,Y;
class coada
{
public:
struct ncoada
{
    int val;
    ncoada* next;
}*primul,*ultimul;
    coada(int a)
    {
        primul=new ncoada;
        primul->val=a;
        ultimul=primul;
        primul->next=NULL;

    }
    void push(int a)
    {
        if(primul)
        {
            ncoada *p=new ncoada;
            ultimul->next=p;
            p->val=a;
            ultimul=p;
            ultimul->next=NULL;
        }
        else
        {
            primul=new ncoada;
            primul->val=a;
            ultimul=primul;
            primul->next=NULL;
        }

    }
    int pop(int a)
    {
        ncoada *p=primul;
        primul=primul->next;
        delete p;
        return a;
    }
    int empty()
    {
        if(primul)
            return 0;
        else return 1;
    }
};
struct graf{
    int vecin;
    graf* urm;
}*v[NMAX];
void add(int nod, int vecin)
{
    graf * p=new graf;
    p->urm=v[nod];
    p->vecin=vecin;
    v[nod]=p;
    p=new graf;
    p->urm=v[vecin];
    p->vecin=nod;
    v[vecin]=p;
}
void citire()
{
    int x,y;
    fin>>N>>M>>S>>Y;
    while(M--)
    {
        fin>>x>>y;
        add(x,y);
    }
}
void parcurgere()
{
    coada coad(S);
    now=S;
    do
    {
        now=coad.primul->val;
        graf* p=v[coad.pop(now)];
        while(p)
        {
            if(poz[p->vecin]==0)
            {
                coad.push(p->vecin);
                if(L[p->vecin]>L[now]+1)
                    L[p->vecin]=L[now]+1;
                poz[p->vecin]=1;
            }
            p=p->urm;
        }
    }while(!coad.empty());
}
void parcurgere_inapoi()
{
    coada coadb(Y);
    now=Y;
    nr=0;
    int n=0;
    graf *p=v[coadb.pop(now)];
    while(p)
    {
        if(L[now]==L[p->vecin]+1)
        {
            nr++;
            ap[now]++;
            coadb.push(p->vecin);
        }
        p=p->urm;
    }
    n=-1;
    do
    {
        now=coadb.primul->val;
        graf *p=v[coadb.pop(now)];
        while(p)
        {
            if(L[now]==L[p->vecin]+1)
            {
                n++;
                if(ap[now])
                    ap[now]++;
                else
                {
                    coadb.push(p->vecin);
                    ap[now]++;
                }
            }
            p=p->urm;
        }
        if(n>0)
            nr=nr+n;
        n=-1;
    }while(!coadb.empty());
}
void afisare()
{
    int max=0;
    ap[Y]=ap[S]=nr;
    for(int j=1;j<=N;++j)
        if(max<ap[j])
            max=ap[j];
    fout<<max<<"\n";
    for(int j=1;j<=N;++j)
        if(max==ap[j])
        fout<<j<<" ";
}

int main()
{
    citire();
    for(int j=1;j<=N;++j)
        if(j!=S)
            L[j]=inf;
    parcurgere();
    parcurgere_inapoi();
    afisare();


    return 0;
}

[•sulzandrei]

e doar 1 drum 2 reprezinta numaru de varfuri comune

[•FlorinHaja]

Am încercat să scriu pentru testul 4 așa cum e în OK-ul de la OJI (știu că e o mulțime de 3 elemente: 58, 59 și 60, iar N-ul este 2), însă tot 90 de puncte îmi dă. Ce e greșit în rezolvarea mea?
Sursă: http://www.infoarena.ro/job_detail/1701023

[•AlexandruValeanu]

Asta este sigur gresit in codul tau:

Cod:

if (n2 == 3 && sol[1] == 58 &&      // Test scris prost.
   sol[2] == 59 && sol[3] == 60)
  g << 2 << '\n';

Cel mai probabil testele au fost adaugate in alta ordine (sau sunt shiftate cu +/- 1).

[•FlorinHaja]

Cel mai probabil testele au fost adaugate in alta ordine (sau sunt shiftate cu +/- 1).

Indiferent cum afișez, tot 90 îmi dă. Am trimis și pe .campion. Acolo îmi dă 100.

[•AlexandruValeanu]

Al doilea while se executa de prea multe ori. Ajungi sa scrii peste date in coada (datorita faptului ca este implementata circular). De aici, WA.

Daca inlocuiesti coada cu std::queue o sa iei TLE pe acel test. Repara al doilea while si totul ar trebui sa fie ok.

[•tudorgalatan]

Ce este greșit în această sursă?

Cod:

#include <fstream>
#include <vector>
#include <queue>

using namespace std;

unsigned short int N, M, X, Y;
unsigned short int A, B;

vector <unsigned int> v[7501];
queue <unsigned int> Q1, Q2;
bool seen[7501];
int sol1[7501], sol2[7501];
bool okay;
unsigned int node, cat;
unsigned int i, j, k;

unsigned int solution1, solution2;

int main ()
{
    ifstream fin ("graf.in");
    fin >> N >> M >> X >> Y;
    for (i=1; i<=M; i++)
    {
        fin >> A >> B;
        v[A].push_back(B);
        v[B].push_back(A);
    }
    fin.close();
    Q1.push(X);
    seen[X] = 1;
    sol1[X] = 1;
    while (!Q1.empty())
    {
        node = Q1.front();
        Q1.pop();
        for (i=0; i<v[node].size(); i++)
            if (seen[v[node][i]] == 0)
            {
                seen[v[node][i]] = 1;
                sol1[v[node][i]] = sol1[node] + 1;
                Q1.push(v[node][i]);
            }
    }
    solution1 = sol1[Y];
    Q2.push(Y);
    seen[Y] = 1;
    sol2[Y] = 1;
    while (!Q2.empty())
    {
        node = Q2.front();
        Q2.pop();
        for (i=0; i<v[node].size(); i++)
            if (seen[v[node][i]] == 0)
            {
                seen[v[node][i]] = 1;
                sol2[v[node][i]] = sol2[node] + 1;
                Q2.push(v[node][i]);
            }
    }
    solution2 = sol2[X];
    ofstream fout ("graf.out");
    fout << solution1 << '\n';
    if (solution1 == 2)
        fout << X << ' ' << Y;
    else
        for (i=1; i<=N; i++)
            if (sol1[i]*sol2[i] == sol1[Y])
                fout << i << ' ';
    fout.close();
    return 0;
}

[•klamathix]

E puțin probabil ca cineva să-ți facă debug pe sursă. E mai productiv pentru toată lumea să faci asta singur, căutând teste mici sau scriind un generator de teste.

[•usureluflorian]

Salut! Ma poate ajuta si pe mine cineva sa inteleg primul exemplul va rog? Eu am desenat graful pe foaie si vad 3 lanturi:  1-3-5-4; 1-2-5-4; 1-6-5-4, toate sunt optime, deci in componenta lanturilor optime intra nodurile 1,2,3,4,5,6, adica toate (in viziunea mea). De ce nu e asa si in exemplu? (eu iau 50 puncte cu logica mea, jumatate din teste incorecte)

[•Bodo171]

Se cer nodurile care apar in toate lanturile optime.Trebuie sa afisezi un nod doar daca el apartine tututor lanturilor.Cu alte cuvinte,trebuie sa afisezi intersectia tuturor laturilor optime,nu reuniunea lor.