Cod sursa(job #3296887)

Utilizator winemomComan Erin winemom Data 18 mai 2025 13:05:41
Problema Flux maxim Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>
using namespace std;
ifstream input("maxflow.in");
ofstream output("maxflow.out");

const int nMax = 1005, INF = 1e9 + 1e5;
int n, m, u, v, cost;
vector<int> g[nMax];
int c[nMax][nMax], f[nMax][nMax];
bool viz[nMax];
int tat[nMax];
queue<int> q;
int flow;

bool bfs(int start)
{
    q.push(start);
    memset(viz, 0, sizeof(viz));
    viz[start] = 1;
    while(!q.empty())
    {
        int node = q.front();
        q.pop();

        for(auto it: g[node])
        {
            if(viz[it] || c[node][it] == f[node][it])
                continue;;
            viz[it] = 1;
            q.push(it);
            tat[it] = node;
        }
    }
    return viz[n];
}

int main()
{
    input >> n >> m;
    while(m--)
        input >> u >> v >> cost,
        g[u].push_back(v),
        g[v].push_back(u),
        c[u][v] += cost;
    while(bfs(1))
    {
        for(auto it: g[n])
        {
            if(!viz[it] || c[it][n] == f[it][n])
                continue;

            tat[n] = it;
            int fmin = INF;
            for(int node = n; node!=1; node = tat[node])
            {
                fmin = min(fmin, c[tat[node]][node] - f[tat[node]][node]);
            }
            if(fmin == 0)
                continue;

            for(int node = n; node != 1; node = tat[node])
                f[tat[node]][node] += fmin,
                f[node][tat[node]] -= fmin;

            flow += fmin;
        }
    }
    output << flow;
}