Cod sursa(job #2608981)

Utilizator vladm98Munteanu Vlad vladm98 Data 1 mai 2020 23:30:36
Problema Flux maxim de cost minim Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.28 kb
#include <bits/stdc++.h>

using namespace std;
int flux[1001][1001], capacitate[1001][1001];

class cmp {
public:
    bool operator () (const pair <int, int> &A, const pair <int, int> &B) const {
        return A.second > B.second;
    }
};
priority_queue <pair <int, int>, vector <pair <int, int>>, cmp> sol;

int tata[1001];
int s, d;
int viz[1001];
int dist[1001];
int n;
vector <pair <int, int>> graf[1001];
bool maxflow (int nod)
{
    dist[nod] = 0;
    sol.push({nod, dist[nod]});
    bool verif = 0;
    while (!sol.empty())
    {
        int node = sol.top().first;
        int cost = sol.top().second;
        sol.pop();
        if (node == d) {
            verif = 1;
        }
        if (dist[node] != cost) continue;
        for (auto x:graf[node])
        {
            if (capacitate[node][x.first]>flux[node][x.first] && dist[x.first]>dist[node]+x.second)
            {
                tata[x.first] = node;
                dist[x.first] = dist[node]+x.second;
                sol.push({x.first, dist[x.first]});
            }
        }
    }
    return verif;
}

int distBellman[1001];

void buildDist() {
    queue <int> Q;
    Q.push(s);
    for (int i = 1; i <= n; ++i) {
        distBellman[i] = 1000000000;
    }
    distBellman[s] = 0;
    while (Q.size()) {
        int node = Q.front();
        Q.pop();
        for (auto x : graf[node]) {
            if (distBellman[x.first] > distBellman[node] + x.second) {
                distBellman[x.first] = distBellman[node] + x.second;
                Q.push(x.first);
            }
        }
    }
    vector <pair <pair <int, int>, int>> edges;
    for (int i = 1; i <= n; ++i) {
        for (auto &x : graf[i]) {
            x.second += distBellman[i] - distBellman[x.first];
            edges.push_back({{i, x.first}, x.second});
        }
    }
//    for (int i = 1; i <= n; ++i) {
//        cout << distBellman[i] << ' ';
//    }
//    cout << '\n';
    for (auto x : edges) {
//        cout << x.first.first << ' ' << x.first.second << ' ' << x.second << '\n';
        graf[x.first.second].push_back({x.first.first, -x.second});
    }
}
int main()
{
    ifstream fin ("fmcm.in");
    ofstream fout ("fmcm.out");
    int m, fluxul = 0;
    fin >> n >> m >> s >> d;
    for (int i = 1; i<=m; ++i)
    {
        int x, y, cap, cost;
        fin >> x >> y >> cap >> cost;
        graf[x].push_back(make_pair(y, cost));
//        graf[y].push_back(make_pair(x, -cost));
        capacitate[x][y] += cap;
    }
    buildDist();
    for (int i = 1; i<=n; ++i)
        dist[i] = 1<<30;
    for (; maxflow(s);)
    {
        int minim = 1<<30;
        int copie = d;
        while (copie!=s)
        {
            if (minim > capacitate[tata[copie]][copie]-flux[tata[copie]][copie])
                minim = capacitate[tata[copie]][copie]-flux[tata[copie]][copie];
            copie = tata[copie];
        }
        if (minim == 0)
            continue;
        fluxul+=(minim*(dist[d] + distBellman[d] - distBellman[s]));
        copie = d;
        while (copie!=s)
        {
            flux[tata[copie]][copie]+=minim;
            flux[copie][tata[copie]]-=minim;
            copie = tata[copie];
        }
        memset(tata, 0, sizeof(tata));
        for (int i = 1; i<=n; ++i)
            dist[i] = 1<<30;
        memset(viz, 0, sizeof(viz));
    }
    fout << fluxul;
    return 0;
}