Cod sursa(job #2416823)

Utilizator stelian2000Stelian Chichirim stelian2000 Data 28 aprilie 2019 12:20:49
Problema Flux maxim de cost minim Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.23 kb
#include <bits/stdc++.h>

using namespace std;

const int inf=1e9;

struct edge
{
    int x,c;
    bool operator <(const edge &aux) const
    {
        return c>aux.c;
    }
};

int sursa,dest,cap[355][355],n,dist[355],d[355],aux[355],tata[355];
char vaz[355];
vector<edge> v[355];
queue<int> q;
priority_queue<edge> mq;

void bellman()
{
    for(int i=1;i<=n;i++) dist[i]=inf;
    dist[sursa]=0;
    vaz[sursa]=1;
    q.push(sursa);
    while(!q.empty())
    {
        int nod=q.front();
        q.pop();
        vaz[nod]=0;
        for(int i=0;i<v[nod].size();i++)
        {
            int vec=v[nod][i].x,c=v[nod][i].c;
            if(cap[nod][vec]>0 && dist[nod]+c<dist[vec])
            {
                dist[vec]=dist[nod]+c;
                if(vec!=dest && !vaz[vec]) {vaz[vec]=1;q.push(vec);}
            }
        }
    }
}

int go()
{
    for(int i=1;i<=n;i++) d[i]=aux[i]=inf;
    d[sursa]=aux[sursa]=0;
    mq.push({sursa,0});
    while(!mq.empty())
    {
        int nod=mq.top().x,c=mq.top().c;
        mq.pop();
        if(d[nod]<c) continue;
        for(int i=0;i<v[nod].size();i++)
        {
            int vec=v[nod][i].x,c1=v[nod][i].c;
            if(cap[nod][vec]>0 && d[nod]+dist[nod]+c1-dist[vec]<d[vec])
            {
                d[vec]=d[nod]+dist[nod]+c1-dist[vec];
                aux[vec]=aux[nod]+c1;
                tata[vec]=nod;
                if(vec!=dest) mq.push({vec,d[vec]});
            }
        }
    }
    for(int i=1;i<=n;i++) dist[i]=aux[i];
    return d[dest]<inf;
}

int main()
{
    freopen("fmcm.in","r",stdin);
    freopen("fmcm.out","w",stdout);
    int m,ans=0,x,y,c1,c2;
    scanf("%d%d%d%d",&n,&m,&sursa,&dest);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&x,&y,&c1,&c2);
        v[x].push_back({y,c2});
        v[y].push_back({x,-c2});
        cap[x][y]=c1;
    }
    bellman();
    while(go())
    {
        int s=inf;
        for(int nod=dest;nod!=sursa;nod=tata[nod]) s=min(s,cap[tata[nod]][nod]);
        for(int nod=dest;nod!=sursa;nod=tata[nod])
        {
            cap[tata[nod]][nod]-=s;
            cap[nod][tata[nod]]+=s;
        }
        ans+=s*dist[dest];
    }
    printf("%d",ans);
    return 0;
}