Cod sursa(job #2048499)

Utilizator rangal3Tudor Anastasiei rangal3 Data 26 octombrie 2017 08:48:44
Problema Flux maxim de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb
#include <fstream>
#include <queue>
#include <bitset>
#include <vector>
#define file "fmcm"
#define N 355
#define oo 1e7

using namespace std;

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

int n,m,s,d,x,y,c,z;
int cc[N][N],zz[N][N],f[N][N];// cc - capacitate, zz - cost, f - flux
int Min = 0; //cel mai negativ cost

int ant[N],dist[N];
priority_queue<pair<int,int> > q;

vector<int> g[N]; //muchii

bitset<N> viz;

void citire()
{
    fin>>n>>m>>s>>d;

    while(m--)
    {
        fin>>x>>y>>c>>z;
        g[x].push_back(y);
        g[y].push_back(x);
        cc[x][y] = c;
        //cc[y][x] = 0
        zz[x][y] = z;
        zz[y][x] = -z;

        Min = min(Min, min(z,-z));
    }

    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
            zz[i][j] -= Min;
}

inline int Dijkstra()
{
    viz.reset();
    for(int i=1; i<=n; ++i)
        dist[i] = oo;

    dist[s] = 0;

    q.push(make_pair(0,s));

    int nod,nodurm,costurm;

    while(!q.empty())
    {
        nod = q.top().second;
        q.pop();

        if(viz[nod] == 1) continue;
        viz[nod] = 1;

        for(int i=0; i<g[nod].size(); ++i)
        {
            nodurm = g[nod][i];
            costurm = zz[nod][nodurm];

            if(dist[nodurm] > dist[nod] + costurm && cc[nod][nodurm] - f[nod][nodurm] > 0)
            {
                ant[nodurm] = nod;
                dist[nodurm] = dist[nod] + costurm;
                q.push(make_pair(-dist[nodurm],nodurm));
            }
        }
    }

    int fluxmin = oo;

    for(int nod = d; nod != s; nod = ant[nod])
        fluxmin = min(fluxmin,cc[ant[nod]][nod] - f[ant[nod]][nod]);


    int ctm = 0;

    for(int nod = d; nod != s; nod = ant[nod],++ctm)
    {
        f[ant[nod]][nod] += fluxmin;
        f[nod][ant[nod]] -= fluxmin;
    }

    return fluxmin * (dist[d]-3*Min);
}

int main()
{
    citire();

    int flux = 0,sol = 0;

    do
    {
        flux += sol;
        sol = Dijkstra();
    }while(sol != 0);

    fout<<flux<<"\n"<<Min;

    return 0;
}