552 Dcmcp

[•DITzoneC]

Aici puteţi discuta despre problema Dcmcp.

[•cos_min]

Cum poti sa folosesti de mai multe ori un vector, adica dupa fiecare citire sa ai size actuale, totul sa fie ok. Eu am incercat ceva de genul(vezi mai jos), dar iau Killed by Signal 11.

vector< vector<int> > L, Cost, Flow;

for ( int k = 1; k <= T; k++ )
    {
        scanf("%d%d%d", &N, &M, &W);
       
        L.resize(N+1); Cost.resize(N+1); Flow.resize(N+1);
       
        for ( int i = 1; i <= M; i++ )
        {
            scanf("%d%d", &x, &y );
            scanf("%d", &c);
            scanf("%d", &t);       
           
            if ( x > N || y > N ) continue;
                 
            L[ x ].push_back(y); L[y].push_back(x);
            Cost[ x ].push_back(t); Cost[y].push_back(t);
            Flow[ x ].push_back(c); Flow[y].push_back(c);
            F[ i ] = c;
        }
        //...//
       
        for ( int i = 0; i < L.size(); i++ )
            L[ i ].clear(), Cost[ i ].clear(), Flow[ i ].clear();
       
        L.clear(), Cost.clear(), Flow.clear();
    }

[•pauldb]

Cod:

vector <int> a;
vector <int> ().swap(a);

[•cos_min]

Merci, ii interesant cu swap  .

Dar se pare ca eu greseam altceva, o dimensiune la un sir. Cel putin acum iau wa.

LE : Tot timpul va exista solutie ?

[•blasterz]

interesant...

cu bellman-ford cu coada scot 1128 ms
iar cu dijkstra cu heapuri  1040 ms
sunt testele slabe?
sau bellman-ford-ul cu coada
se comporta chiar bine?

[•mugurelionut]

in general, bellman-ford cu coada se comporta foarte bine. sunt putine probleme unde poti sa busesti acest tip de solutie (una din ele e problema "The Queen", de pe SGU : http://acm.sgu.ru/problem.php?contest=0&problem=235 ; dar si acolo, daca optimizezi mai multe chestii, toti poti sa iei AC). eu nu cred ca sunt testele slabe, dar, totusi, as fi curios daca reuseste cineva sa gaseasca vreun test la aceasta problema pe care bellman-ford cu coada sa mearga prost (si daca gasiti un astfel de test, va rog sa-mi spuneti si mie, ca sa imbunatatesc testele problemei ).

[•Dastas]

Daca are cineva chef sa se uite peste sursele astea 2 si sa-mi explice de ce una ia 100 si cealalta 0, i-as fi super recunoscator...

http://infoarena.ro/job_detail/110845
http://infoarena.ro/job_detail/110843

Singura diferenta este comentariul de pe linia 53.

Practic, cu comentariu iau sigsegv, fara iau 100. Acel vector nu e folosit niciunde in program, si nu-mi dau seama cum ar putea influenta ceva lipsa lui...

[•wefgef]

Ia sursa de 100, decomenteaza linia 53, si vei lua 100.

Nu exista o singura diferenta.

Liniile 228 si 230, ai schimbat din long long in int. Apelezi functia dmin2, care are ca parametru o variabila de tip int, iar tu ii transmiti un long long. Din aceasta cauza programul tau merge aiurea. Castul din long long in int nu se face prea bine se pare.

[•Dastas]

Da, asa e. M-am grabit. Tot am comentat si decomentat portiuni si schimbat tipuri de date si nu mai stiam de ce ba iau 100 ba 0...

Mersi .