Cod sursa(job #3372148)

Utilizator iustincmbMaican Iustin iustincmb Data 2 noiembrie 2026 17:14:37
Problema Flux maxim de cost minim Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4 kb
#include <bits/stdc++.h>
using namespace std;
struct CostEdge
{
    int to;
    long long int capacity;
    long long int cost;
};

struct MinCostFlow
{
    //??
    static constexpr long long INF=LLONG_MAX/4;
    vector<CostEdge>edges;
    vector<vector<int>> outEdges;
    vector<long long>potential;
    
    MinCostFlow(int nodeCount) : outEdges(nodeCount), potential(nodeCount, 0) {}
    
    void addEdge(int from, int to, long long capacity, long long cost)
    {
        outEdges[from].push_back(edges.size());
        edges.push_back({to, capacity, cost});
        outEdges[to].push_back(edges.size());
        edges.push_back({from, 0, -cost});
    }
    
    // SPFA
    void initPotentials(int source)
    {
        int n=outEdges.size();
        vector<long long>dist(n, INF);
        vector<char>inQueue(n, 0);
        deque<int>q;
        dist[source]=0; q.push_back(source);
        while(!q.empty())
        {
            int v=q.front(); q.pop_front(); inQueue[v]=0;
            for(int id : outEdges[v])
            {
                const CostEdge &e=edges[id];
                if(e.capacity>0 && dist[v]+e.cost<dist[e.to])
                {
                    dist[e.to]=dist[v]+e.cost;
                    if(!inQueue[e.to])
                    {
                        inQueue[e.to]=1;
                        q.push_back(e.to);
                    }
                }
            }
        }
        for(int v=0; v<n; v++)
        {
            if(dist[v]==INF)
                potential[v]=0;
            else
                potential[v]=dist[v];
        }
    }
    
    pair<long long, long long> run(int source, int sink, long long maxUnits)
    {
        int n=outEdges.size();
        long long int sent=0, totalCost=0;
        while(sent<maxUnits)
        {
            // We do Dijkstra on reduced prices cost+pi(v)-pi(to) (all>=0)
            vector<long long>dist(n, INF);
            vector<int> parentEdge(n, -1);
            priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>>pq;
            dist[source]=0; pq.push({0, source});
            while(!pq.empty())
            {
                auto [d, v]=pq.top(); pq.pop();
                if(d!=dist[v])
                    continue; // outdated value entry, already smth better
                for(int id : outEdges[v])
                {
                    const CostEdge &e=edges[id];
                    if(e.capacity<=0)
                        continue;
                    long long reduced=e.cost+potential[v]-potential[e.to];
                    if(reduced+dist[v]<dist[e.to])
                    {
                        dist[e.to]=dist[v]+reduced;
                        parentEdge[e.to]=id;
                        pq.push({dist[e.to], e.to});
                    }
                }
            }
            if(dist[sink]==INF) // if we cannot reach the sink
                break;
            for(int v=0; v<n; v++)
            {
                if(dist[v]<INF)
                    potential[v]+=dist[v]; // we update the potentials pi+=d
            }
            long long push=maxUnits-sent; // don t push more that needed
            for(int v=sink; v!=source; v=edges[parentEdge[v]^1].to)
                push=min(push, edges[parentEdge[v]].capacity); // we search for the bottleneck
            
            for(int v=sink; v!=source; v=edges[parentEdge[v]^1].to)
            {
                edges[parentEdge[v]].capacity-=push;
                edges[parentEdge[v]^1].capacity+=push;
                totalCost+=push*edges[parentEdge[v]].cost;
            }
            sent+=push;
        }
        return {sent, totalCost};
    }
    
};
int main()
{
    ifstream cin ("fmcm.in");
    ofstream cout ("fmcm.out");
    int n, m, s, d;
    cin >> n >> m >> s >> d;
    MinCostFlow flux(n+1);
    for(int i=1; i<=m; i++)
    {
        int x, y, c, z;
        cin >> x >> y >> c >> z;
        flux.addEdge(x, y, c, z);
    }
    flux.initPotentials(s);
    pair<long long, long long>val=flux.run(s, d, LLONG_MAX/4);
    cout << val.second << '\n';
    return 0;
}