142 Ciclu

[•Mishu91]

Tu vei găsi 267 (cea mai mică valoare pentru care ai ciclu negativ).

[•new_programmer]

Mersi de idee Andrei, sa nu uitati celor ce nu va da 100 de puncte sa puneti long long.

[•APOCALYPTO]

Salut!
Ce este special la testul 9 pentru ca nu-mi da deloc    .
Multumesc anticipat!

LE Am rezolvat!!

[•Andrei_Scorpio]

Am si eu o intrebare..trebuie sa implementez dinamic sau circular coada la Bellman-Ford? sau cat de mare sa o iau? Iau Killed by signal 11(SIGSEGV) si nu stiu unde iese in porumbi...

[•APOCALYPTO]

Am si eu o intrebare..trebuie sa implementez dinamic sau circular coada la Bellman-Ford? sau cat de mare sa o iau? Iau Killed by signal 11(SIGSEGV) si nu stiu unde iese in porumbi...

La testul 9  ciclul negativ nu se formeaza in 1  Daia nu merge. aceiasi problema am avut si eu.

[•Bogdan_tmm]

Daca fac belman ford cu coada numarand sa nu am mai mult de n*m pasi si apoi verific daca pentru muchiile existente se poate obtine un cost mai mic nu e corect? Iau 0 puncte cu abordarea asta pe cand cu un belman ford fara coada aplicat de n ori si apoi verificarea iau 60.

[•vendetta]

Am o cautare binara + bellman ford si iau 90 de pct cu wa pe ultimul test...

[•S7012MY]

Mareste valoarea pe care o cauti binar

[•SpiderMan]

Aia era, i-am lasat mesaj  .

[•balakraz94]

Imi poate da cineva un test mai mare, ca sa ma verific pana isi revine evaluatorul ?

[•balakraz94]

Se mai pot lua 100p la problema asta cu noua limita de timp ?
Pentru ca am parsat citirea, am luat precizia minima si iau 90p.

[•claudiumihail]

Salut,

Se mai pot lua 100p cu limita actuala de timp (poate s-a marit de cand a intrebat lumea desi ma indoiesc). Ideea e sa modifici putin Bellman Ford-ul sa iasa repede cand detecteaza ca exista un ciclu (fail fast). Iar cealalta idee sa sa faci cautarea binara sa inceapa de la o valoarea cat de cat apropiata de costum mediu minim (astfel incat sa faci cat mai putine apeluri catre Bellman Ford). Poti gasi o euristica ceva pentru valoarea de inceput. Eu asa am facut.

Sper sa ajute pe cineva indicatiile,
Claudiu

[•valentin.harsan]

cred ca nu se mai poate lua 100 cu noua limita de timb 
am trimis o sursa care lua 100 si a luat 90 cu TLE pe ultimu test 

[•S7012MY]

Se  poate lua 100 si cu noua limita de timp

[•Fayed]

Vreau sa gasesc cea mai mare valoare intre 2 numere cunoscute de tip float. Acea valoare o voi scadea pe toate muchiile unui graf, astfel incat sa nu obtin ciclu negativ daca aplic algoritmul Bellman Ford.
Eu am incercat ceva si nu inteleg ce nu merge. Mie mijloc imi returneaza la final ca fiind 1.5 si eu trebuie sa obtin 1.75.Ma intereseaza cel mai mult de ce nu merge cand caut binar in main, in rest cred ca am facut bine. Iata sursa mea:

#include <cstdio>
#include <vector>
#include <list>
#include <utility>
#include <queue>
#include <cstring>
#include <iomanip>
#define inf 1000000
#define NMAX 1001
using namespace std;

typedef pair<int,float> pereche;
vector < list < pereche > > Graf;
queue < int > q;
int inQueue[NMAX],vizitat[NMAX];
vector < int > aparitii;
vector < float > d;
int n,m,scaderi;
float minim = inf;

void citesc(){

    int x,y;
    float c;
    freopen("ciclu.in","r",stdin);
    freopen("ciclu.out","w",stdout);
    scanf("%d%d",&n,&m);
    Graf.resize(n+1);
    d.resize(n+1);
    aparitii.resize(n+1);
    for(register int i=1;i<=m;++i){
        scanf("%d%d%f",&x,&y,&c);
        Graf
.push_back(pereche(y,c));
        Graf[y].push_back(pereche(x,c));
        if(c < minim)
            minim = c;
    }
}

void DFS(int nod){

    vizitat[nod] = 1;
    for(list < pereche >::iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
        if(!vizitat[it->first]){
            it->second -= minim;
            DFS(it->first);
    }}

int Bellman_Ford(int nod){

    int top;
    q.push(nod);
    inQueue[nod] = 1;
    ++aparitii[nod];
    d[nod] = 0;
        while(!q.empty()){
            top = q.front();
            q.pop();
            inQueue[top] = 0;
                for(list <pereche>::iterator it = Graf[top].begin();it!=Graf[top].end();++it)
                    if(d[it->first] > d[top] + it->second){
                        d[it->first] = d[top] + it->second;
                        if(!inQueue[it->first]){
                            inQueue[it->first] = 1;
                            q.push(it->first);
                        }
                    ++aparitii[it->first];
                    if(aparitii[it->first] >= n)
                    return 0;
            }
        }
return 1;
}

int main(){

    citesc();
    DFS(1);
        scaderi++;
 d.assign(n+1,inf);
 while(Bellman_Ford(1)){
            d.assign(n+1,inf);
            memset(vizitat,0,sizeof(vizitat));
            aparitii.assign(n+1,0);
            DFS(1);
        scaderi++;
        }

   float inceput = (scaderi-1)*minim;
   float sfarsit = scaderi*minim;
   float mijloc = 0;

        while(inceput <= sfarsit){

            memset(vizitat,0,sizeof(vizitat));
            aparitii.assign(n+1,0);
            d.assign(n+1,inf);

            mijloc = (inceput+sfarsit)/2;
            minim = mijloc;
            DFS(1);
            if(!Bellman_Ford(1))
            sfarsit = mijloc-1;
            else
            inceput = mijloc+1;

        }

printf("%d\n",scaderi);
printf("%f",mijloc);
return 0;
}

[•RaduDo]

Imi poate da si mie cineva un test fiindca pe toate testele incercate imi merge, insa iau numai 20 de puncte?..
Multumesc anticipat!