Cod sursa(job #825194)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 27 noiembrie 2012 20:15:44
Problema Flux maxim de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.42 kb
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

const int nmax= 350, inf= 1<<30;

struct str{
    int x, y;
};

int n;
vector <int> g[nmax+1];
int cpc[nmax+1][nmax+1], cst[nmax+1][nmax+1];

bool uq[nmax+1];
int bf[nmax+1], cbf[nmax+1];
queue <int> q;

struct cmp_str{
    bool operator()(str a, str b){
        return a.y>b.y;
    }
};

int djk[nmax+1], p[nmax+1];
priority_queue <str, vector <str>, cmp_str> h;

bool dijkstra(int s, int d){
    for (int i= 1; i<=n; ++i){
        djk[i]= inf;
    }
    djk[s]= 0;
    str aux;
    aux.x= s; aux.y= 0;
    h.push(aux);

    while (!h.empty()){
        int x= h.top().x, y= h.top().y;
        h.pop();
        if (y==djk[x]&& x!=d){
            for (vector <int>::iterator it= g[x].begin(); it!=g[x].end(); ++it){
                if (cpc[x][*it]>0&& djk[*it]>djk[x]+cst[x][*it]){ 
                    aux.x= *it; aux.y= djk[x]+cst[x][*it];
                    h.push(aux);
                    djk[*it]= aux.y;
                    p[*it]= x;
                }
            }
        }
    }

    return djk[d]!=inf;
}

int main(){
    int m, s, d;
    fin>>n>>m>>s>>d;
    for (int i= 1; i<=m; ++i){
        int x, y;
        fin>>x>>y;
        g[x].push_back(y); g[y].push_back(x);
        fin>>cpc[x][y]>>cst[x][y];
        cst[y][x]= -cst[x][y];
    }

    for (int i= 1; i<=n; ++i){
        bf[i]= inf;
    }
    bf[s]= 0;
    q.push(s); uq[s]= 1;
    
    while (!q.empty()){
        int x= q.front();
        q.pop(); uq[x]= 0;
        
        for (vector <int>::iterator it= g[x].begin(); it!=g[x].end(); ++it){
            if (cpc[x][*it]>0&& bf[*it]>bf[x]+cst[x][*it]){
                bf[*it]= bf[x]+cst[x][*it];
                if (!uq[*it]){
                    q.push(*it); uq[*it]= 1;
                }
            }
        }
    }
    
    for (int i= 1; i<=n; ++i){
        for (vector <int>::iterator it= g[i].begin(); it!=g[i].end(); ++it){
            cst[i][*it]+= bf[i]-bf[*it];       
        }
    }

    int mf= 0, mc= 0;
    while (dijkstra(s, d)){
        int aux= inf;
        for (int i= d; i!=s; i= p[i]){
            if (aux>cpc[p[i]][i]){
                aux= cpc[p[i]][i];
            }
        }
        mf+= aux;
        mc+= aux*(djk[d]+bf[d]);
        for (int i= d; i!=s; i= p[i]){
            cpc[p[i]][i]-= aux;
            cpc[i][p[i]]= aux;
        }
    }
    fout<<mf<<" "<<mc<<"\n";

    return 0;
}