multumesc

si eu sper sa apuc ziua sa nu mai fie nevoie ...

sabbath

Buna,

va uitati peste alg tarjan ...
astept o idee
Sursa este mai sus.


Multumesc!

Buna

Va rog cine are timp... Am nevoie de ajutor.

Cod:

#include <fstream>
#include <stdio.h>
#include <stack>

using namespace std;

struct nod
{
    int inf;
    nod *urm;
}*L[100000];



int n,m;
int viz[100001], low[100001], in, vizs[100001];
stack <int> S;

void add(nod *&prim, int vec)
{
    nod *p= new nod;
    p->inf = vec;
    p->urm = prim;
    prim = p;
}



void citire()
{

    scanf("%d %d",&n,&m);

    for (int i = 0; i < m; i++)
   {
        int x,y;
        scanf("%d %d",&x,&y);
        add(L[x], y);
    }
}

void tarjan(int v)//indicele nodului din care plec
{
    viz[v] = in;
    low[v] = in;
    in++;
    S.push(v);
    vizs[v] = 1;
    for(nod *p=L[v]; p; p=p->urm)
        if(viz[p->inf] == 0)
            {
                tarjan(p->inf);
                low[v] = min(low[v], low[p->inf]);
            }
        else
            if(vizs[p->inf] == 1)
                low[v] = min(low[v], viz[p->inf]);

 int x;
    if(viz[v] == low[v])
    do
    {
        x = S.top();
        printf("%d ", x);
        vizs[x] = 0;
        S.pop();
    }while(v != x );


}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    citire();
    for(int i=1;i<=n;i++)
        if(viz[ i ] == 0)
        {
            tarjan(i);
            printf("\n");
        }
    return 0;
}

Multumesc frumos!

Buna,

mi-ati putea spune cum vad testele de la problema parcurgere in latime?

[Editat de moderator: Foloseste [ code]...[/ code] cand postezi secvente de cod. Este a treia oara cand ti se atrage atentia asupra acestui lucru.]

Backtrackingul l-am inteles ... stiu sa fac permutari, dar nu stiu cum sa pun  in solutie ...

Cod:

void back()
{
    if(k == n)
         //aici am vectorul sol... ce sa fac cu el aplic Dijkstra()... dar nu este acelasi???? disjkstra(ff, f[1]), dijkstra(f[1] , f[2] ) ...

    else
         for(int i=1;i<=n;i++)
             if(s[f[i]] == 0)
                {
                   s[f[i]] = 1;
                   sol[k] = f[i];
                   back(k+1);
                   s[f[i]] = 0;
                }

cum sa verific daca este buna solutia? care este criteriul? daca aplic o singura data Dijkstra nu obtin distanta minima la fiecare ... conteaza cum formez solutia de ce?
multumesc Florian!


am inceput sa ma prind;


dijkstra aplic de 5 ori, cate fete sunt, salvez distantele si vectorul tata pentru fiecare dintre acestea intr-o matrice; apoi fac backtracking pentru sirul feteleor si calculez distanta pt fata data ---ff, f1, f2, f3, f4, f5, si o camera din care ies pana gasesc suma minima



Editat de moderator: Foloseste [ code]...[/ code] cand postezi secvente de cod. Este a treia oara cand ti se atrage atentia asupra acestui lucru.

Buna

Nu am inteles ce sa sciu in backul acela ...
Ce s afac distanta

Cod:

void back()
{
    if()
       {}
    else
         {
          for(int i=1;i<=5;i++)

}
}

nu stiu cum s ama apuc de problema asta ... m-am prins ca etse graf neorientat... backul, grafurile le invat de capul meu ... nu le-am facut inca ... multumesc de ajutor

Foloseste tag-ul [ code ] [/ code ] cand postezi cod. Exista un buton ajutator deasupra emoticoanelor. Nu posta consecutiv pe aceeasi tema, modifica mesajele anterioare.

Buna
nu stiu daca am voie sa postez sursa aici ... inca nu m-am prins unde am gresit ...

[Later edit] asta este sursa pe care am scris-o pt zmeu ...
daca poate sa imi dea careva o idee ...

Cod:

#include <iostream>

using namespace std;


int n,m,p,ff, f[5], mat[1000][1000], ies[500], viz[1000], d[1000], pre[1000], ;//nr de camere, tunele, iesiri

void citire()
{
    freopen("zmeu.in", "r", stdin);

    scanf("%d%d%d/n", &n, &m, &p);
    scanf("\n");
    scanf("%d", &ff);

    for(int i=1;i<=5;i++)
        scanf("%d", &f[i]);
    scanf("\n");
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d", &a, &b, &c);
        mat[a][b] = c;
        mat[b][a] = c;
    }
    for(int i=1;i<=p;i++)
        scanf("%d\n",&ies[i] );
    for(int i =1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i != j && mat[i][j] == 0)
                mat[i][j] = 333;

}
int dijkstra()
{
   for(int i=1;i<=n;i++)
   {
       d[i] = mat[ff][i];
       pre[i] = ff;
   }
   viz[ff] = 1;
   pre[ff] = 0;
   int pozmin;
   for(int j=1;j<=n;j++)
   {
       int dmin = 333;
       for(int i=1;i<=n;i++)
        if(viz[i] == 0 && dmin > d[i])
        {
            dmin = d[i];
            pozmin = i;
        }
       viz[pozmin] = 1;
       for(int i=1;i<=n;i++)
        if(viz[i] == 0 && d[i]> dmin + mat[pozmin][i])
        {
            d[i] = dmin + mat[pozmin][i];
            pre[i] = pozmin;
        }
   }
   int s = 0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            if(i == j)
                s = s + d[i];
    }
}

void afisare()
{
    freopen("zmeu.out", "w", stdout);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            printf("%d ", mat[i][j]);
        printf("\n");
    }
    printf("\n");
      printf("%d",dijkstra());
}



int main()
{
    citire();
    afisare();
    dijkstra();

    return 0;
}

Editat de moderator: Foloseste tagul [ code ] cand postezi cod si editeaza-ti mesajele mai vechi in loc sa postezi de 2 ori consecutiv.

Buna

Se vorbeste despre problema zmeu:
Zmeul le-a inchis pe cele 5 fete ale imparatului in castelul sau. Fat-Frumos a venit sa le scoata din castel, folosind harta pe care i-a dat-o zana buna. Pe harta sunt desenate cele n camere ale castelului, numerotate de la 1 la n si cele m tuneluri dintre camere. De asemenea sunt marcate camerele in care se gasesc fetele si Fat-Frumos, timpul necesar traversarii fiecarui tunel si cele p camere din care se poate iesi din castel.

Cerinta

Determinati timpul minim necesar lui Fat-Frumos pentru a lua cele 5 fete si a le scoate din castel.

Date de intrare

Pe prima linie a fisierului de intrare zmeu.in sunt scrise numerele n, m si p, reprezentand numarul de camere, numarul de tunele si respectiv numarul de iesiri din castel.
Pe a doua linie sunt scrise numerele a 6 camere distincte: primul numar e camera in care se afla Fat-Frumos, iar celelalte 5 sunt camerele fetelor.
Pe urmatoarele m linii sunt cate 3 numere, reprezentand cele m tunele: primele doua reprezinta camerele intre care face legatura tunelul, al treilea timpul necesar traversarii tunelului.
Ultimele p linii contin cate un numar reprezentand camerele din care se poate iesi din castel. Toate numerele sunt intregi strict pozitive, iar numerele de pe aceeasi linie sunt separate prin cate un spatiu.

Date de iesire

Prima linie a fisierului zmeu.out va contine un singur numar, timpul minim necesar pentru a porni din camera lui Fat-Frumos, a trece prin camerele celor 5 fete si a ajunge intr-o camera care are iesire in afara. Se va lua in considerare numai timpul traversarii tunelurilor, neglijandu-se timpul traversarii camerelor sau a iesirii din castel.

Am incercat sa rezol problema. Rezultate: fetele mi le afiseaza corect, dar nu imi iese suma ... am lucrat cu Dijkstra fara heapuri.
Daca cineva ma poate ajuta cu o idee...