infoarena

Aici puteţi discuta despre problema Ciclu (http://infoarena.ro/problema/ciclu).

nu pricep o kestie ... calculez costul mediu al unui cilcu .... adica indiferent care ? sau caut ciclul cu costul mediu minim ?

Logic ca ciclul de cost mediu care sa fie MINIM, adica toate celelalte cicluri au costul mediu mai mare decat cel determinat ca fiind minim.

Pai e suficient numai costul, tu cand cauti costul verifici doar daca exista un ciclu cu costul respectiv, fara a-l determina.

Daca printez printf("%.2lf\n",sol) e ok?

da

shtiu k suna ... da un ciclu inseamna sa revina in nodul sursa? sau nu?

da

RTM

RTM ? ce ii aia ?  #-o

Read the Manual!  :)

Eu incerc sa determin daca exista un ciclu de cost negativ pornind numai din nodul 1 folosind Bellman Ford cu coada, iar acest ciclu exista cand un nod din cele N a fost scos din coada de N ori. Este adevarat ce am zis, pentru ca obtin doar 60 ?

ciclul cautat nu contine neaparat nodul 1.

Am incercat si asa: am pornit din fiecare nod neexplorat, initializandu-l cu distanta 0, si am aplicat algoritmul lui Bellman Ford cu coada obisnuit si am luat 30.
Poate nu am incercat bine. :)

Nici asa nu e bine. Incearca sa introduci un nod auxiliar S, si muchii orientate de cost 0 de la nodul S la fiecare din celelalte noduri si fa un Bellman Ford din sursa S ( astfel vei determina sigur daca exista vreun ciclu negativ ).

Cum poate exista un ciclu negativ, daca fiecare muchie e strict pozitiva si lungimea ciclului este, evident, tot strict pozitiva?

Se cauta binar costul mediu minim cerut si se scade pe toate muchiile. Pe noile costuri astfel obtinute se cauta ciclul de cost negativ. Daca faci un pic niste formule pe foaie o sa intelegi de ce merge chestia asta.

Imi puteti divulga si mie unul dintre teste va rog ? Algoritmul meu merge pe exemplu si pe toate testele care i le-am dat eu. Totusi iau numai primul test  ](*,) Inca un exemplu mi-ar fi de mare folos...

Nu se dau teste oficiale ...

Nici o problema. Intre timp am descoperit unde am facut greseala. Scuze pentru ce am cerut. Am gresit eu intrebarea, ar fi trebuit doar sa cer cateva teste mari si atat  :shock: , in loc sa cer pe cele oficiale. Multumesc oricum!

Cei cu sursele de 1.3 kb ati folosit programare dinamica sau ati rezolvat cu cautare binara+bellman ford?

Este atât de relevantă dimensiunea sursei? Și apoi, nu prea văd cu ce te-ar ajuta dacă ai ști că cei cu surse de 1,3 au rezolvat printr-o metodă sau alta. Deși nu am sursa de 1,3 kb, am rezolvat prin căutare binara + Bellman - Ford. :)

   Poi ma ajuta sa stiu , deoarece vreau sa stiu daca o iau pe aratura.Eu am o sursa de +3 kb incercand sa fak ce am zis mai sus.
   Daca numarul pe care-l cautam binar e 8/3 cum il gasesti?

Înmulțești costurile tuturor muchiilor cu 100 si cauti un numar intreg, iar când afișezi împarți la 100.

Poi asa faceam , dar de exemplu daka am un graf de genu:
4 5
1 4 5
4 2 5
1 2 1
2 3 3
3 1 4

Ar trebui sa gasesc r=266 care impartit la 100 da 2.66(8/3) pentru ciclu 1-2-3-1.Ca sa fie acest ciclu egal cu 0 ar trebui sa am conditia urmatoare adevarata: 100-r+300-r+400-r=0 <=> -166+34+134=0 <=>166=168 dar e falsa  :-s

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

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

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

LE Am rezolvat!!

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.

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.

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

Mareste valoarea pe care o cauti binar :thumbup:

Aia era, i-am lasat mesaj  :ok:.

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

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.

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

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  ](*,)

Se  poate lua 100 si cu noua limita de timp :)

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

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