Cod sursa(job #1464229)

Utilizator petru.cehanCehan Petru petru.cehan Data 22 iulie 2015 17:40:15
Problema Flux maxim de cost minim Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4.77 kb
#include <iostream>

/*
Flux maxim de cost minim - O(N^2*M*logN)
Implementare folosind algoritmul lui Dijkstra pentru determinarea drumului de crestere
*/

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

#define NMAX 355
#define INF 0x3f3f3f3f
#define pb push_back
#define MIN(a,b) (a<b) ? a : b

using namespace std;

ifstream in("fmcm.in");
ofstream out("fmcm.out");

int N, M, Sursa, Dest, Nod, Cnt, i, x, y, capacitate, cost, CostMin, FluxCt, Total;

int F[NMAX][NMAX], C[NMAX][NMAX]; // matricele de flux si capacitate
int Cost[NMAX][NMAX]; // matricea costurilor arcelor

int CostDrum[NMAX]; // vectorul unde se vor retine costurile minime pana in fiecare nod
int T[NMAX]; // vectorul care ajuta la parcurgerea drumului de cost minim pentru a pompa flux
int H[NMAX], Pos[NMAX]; // vectorii pentru heap si pozitia fiecarui nod in heap - vezi algoritmul lui Dijkstra si/sau prezentarea heap-urilor

vector< int > G[NMAX]; // listele de adiacenta asociate grafului
vector< int >::iterator Vecin;

queue< int > Q; // coada
bool USED[NMAX]; // vectorul care arata daca un nod se afla in coada - vezi algoritmul Bellman-Ford

inline void Swap( int a, int b ) // operatie asociata heap-ului
{
    int aux = H[a];
    H[a] = H[b];
    H[b] = aux;

    Pos[ H[a] ] = a;
    Pos[ H[b] ] = b;
}

inline void HeapDown( int NOD ) // operatie asociata heap-ului
{
    int Fiu = 2*NOD;

    if( Fiu <= Cnt )
    {
        if( Fiu + 1 <= Cnt && CostDrum[ H[Fiu+1] ] < CostDrum[ H[Fiu] ] ) ++Fiu;

        if( CostDrum[ H[Fiu] ] < CostDrum[ H[NOD] ] )
        {
            Swap( Fiu, NOD );
            HeapDown( Fiu );
        }
    }
}

inline void HeapUp( int NOD ) // operatie asociata heap-ului
{
    if( NOD > 1 )
    {
        int T = NOD/2;
        if( CostDrum[ H[T] ] > CostDrum[ H[NOD] ] )
        {
            Swap( T, NOD );
            HeapUp( T );
        }
    }
}

inline void Bellman()
{
    memset( CostDrum, INF, sizeof(CostDrum) );
    CostDrum[Sursa] = 0;

    memset( USED, false, sizeof(USED) );
    Q.push( Sursa );
    USED[Sursa] = true;

    while( !Q.empty() )
    {
        int Nod = Q.front();
        Q.pop();
        USED[Nod] = false;

        for( Vecin = G[Nod].begin(); Vecin != G[Nod].end(); Vecin++ )
            if( F[Nod][*Vecin] < C[Nod][*Vecin] && CostDrum[*Vecin] > CostDrum[Nod] + Cost[Nod][*Vecin] )
            {
                CostDrum[*Vecin] = CostDrum[Nod] + Cost[Nod][*Vecin];
                if( !USED[*Vecin] )
                {
                    Q.push( *Vecin );
                    USED[*Vecin] = true;
                }
            }
    }

    Total = CostDrum[Dest];
}

inline bool Dijkstra()
{
    for( Nod = 1; Nod <= N; Nod++ )
        if( CostDrum[Nod] != INF )
            for( Vecin = G[Nod].begin(); Vecin != G[Nod].end(); Vecin++ )
                if( CostDrum[*Vecin] != INF )
                    Cost[Nod][*Vecin] += CostDrum[Nod] - CostDrum[*Vecin]; // actualizez costurile arcelor sa ajung pe pozitiv

    memset( CostDrum, INF, sizeof(CostDrum) );
    CostDrum[Sursa] = 0;

    memset( T, 0, sizeof(T) );
    for( i = 1; i <= N; i++ )
        H[i] = Pos[i] = i;
    Swap( 1, Sursa );
    Cnt = N;

    while( Cnt && CostDrum[ H[1] ] != INF )
    {
        int Nod = H[1];
        Swap( 1, Cnt-- );
        HeapDown( 1 );

        for( Vecin = G[Nod].begin(); Vecin != G[Nod].end(); Vecin++ )
            if( F[Nod][*Vecin] < C[Nod][*Vecin] && CostDrum[*Vecin] > CostDrum[Nod] + Cost[Nod][*Vecin] )
            {
                CostDrum[*Vecin] = CostDrum[Nod] + Cost[Nod][*Vecin];
                T[*Vecin] = Nod;

                HeapUp( Pos[*Vecin] );
            }
    }

    return ( CostDrum[Dest] != INF ); // vad daca mai exista drum de ameliorare
}

int main()
{
    in >> N >> M >> Sursa >> Dest;
    for( ; M--; )
    {
        in >> x >> y >> capacitate >> cost; //citesc informatiile legate de fiecare arc
        G[x].pb( y ); //construiesc reteaua
        G[y].pb( x );

        C[x][y] = capacitate;
        Cost[x][y] = cost;
        Cost[y][x] = -cost;
    }

    Bellman(); //calculez initial distantele minime cu Bellman Ford

    for( CostMin = 0; Dijkstra(); ) // cat timp am drum de ameliorare
    {
        FluxCt = INF;

        for( Nod = Dest; Nod != Sursa; Nod = T[Nod] )
            FluxCt = MIN( FluxCt, C[ T[Nod] ][Nod] - F[ T[Nod] ][Nod] ); // determin fluxul maxim ce se poate pompa pe toate arcele din drum

        for( Nod = Dest; Nod != Sursa; Nod = T[Nod] )
            F[ T[Nod] ][Nod] += FluxCt, F[Nod][ T[Nod] ] -= FluxCt; // saturez drumul de ameliorare

        Total += CostDrum[Dest];
        CostMin += FluxCt * Total;
    }

    out << CostMin << '\n';

    return 0;
}