Cod sursa(job #3193165)

Utilizator pifaDumitru Andrei Denis pifa Data 14 ianuarie 2024 12:19:54
Problema Flux maxim Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("maxflow.in");
ofstream out("maxflow.out");

const int N = 1e4 + 5;

vector <int> g[N];

int n, m;

const int INF = 2e9;

int cap[N][N], flux[N][N], pred[N];

bool bfs(int s, int t)
{
    memset(pred, 0, sizeof(pred));
    queue <int> q;
    q.push(s);
    pred[s] = -1;
    while(q.size())
    {
        int cur = q.front();
        q.pop();
        if(cur == t)
            return true;
        for(auto next: g[cur])
        {
            if(pred[next] == 0 && flux[cur][next] < cap[cur][next])
            {
                pred[next] = cur;
                q.push(next);
            }
        }
    }
    return false;
}

int bottleneck(int s, int t)
{
    int ans = INF, x = t;
    while(x != s)
    {
        ans = min(ans, cap[pred[x]][x] - flux[pred[x]][x]);
        x = pred[x];
    }
    return ans;
}

void actualizare(int ans, int s, int t)
{
    int x = t;
    while(x != s)
    {
        flux[pred[x]][x] += ans;
        flux[x][pred[x]] -= ans;
        x = pred[x];
    }
}

int flux_maxim(int s, int t)
{
    int ans = 0;
    while(bfs(s, t))
    {
        int minim = bottleneck(s, t);
        actualizare(minim, s, t);
        ans += minim;
    }
    return ans;
}

int main()
{
    in >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y, capacitate;
        in >> x >> y >> capacitate;
        g[x].push_back(y);
        g[y].push_back(x);
        cap[x][y] = capacitate;
    }
    out << flux_maxim(1, n);
    return 0;
}