Cod sursa(job #1864535)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 31 ianuarie 2017 20:36:53
Problema Flux maxim Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

#define f_mare  0x3f3f3f3f
int coada[1005], st, dr, i, j;
int n, m, x, y, z, c[1005][1005], f[1005][1005], sol, fmin, tt[1005];
bool viz[1005];
vector <int> ls[1005];

inline bool umplut(int x, int y) {
    return (c[x][y]-f[x][y] == 0);
}

bool bf() {
    int i, l, x, y;
    memset(viz, 0, sizeof(viz));
    coada[st=dr=1] = 1;
    viz[1] = 1;
    while (st<=dr) {
        x = coada[st++];
        l = ls[x].size();
        viz[1] = 1;
        for (i = 0; i < l; i++) {
            y = ls[x][i];
            if (viz[y]|| umplut(x,y))
                continue;
            viz[y] = 1;
            tt[y] = x;
            coada[++dr] = y;
            viz[y] = 1;
            if (y == n) return 1;
        }
    }
    return 0;
}

int main() {
    in >> n >> m;
    while (m--) {
        in >> x >> y >> z;
        ls[x].push_back(y);
        ls[y].push_back(x);
        c[x][y] += z;
    }
    z = ls[n].size();
    while (bf()) {
        for (j = 0; j < z; j++) {
        y = ls[n][j];
        if (umplut(y,n))
            continue;
        tt[n] = y;
        fmin = f_mare;
        y = n;
        while (y != 1)
            fmin = min(fmin, c[tt[y]][y]-f[tt[y]][y]), y = tt[y];
        if (fmin == 0)
            continue;
        y = n;
        while (y != 1) {
            f[tt[y]][y] += fmin;
            f[y][tt[y]] -= fmin;
            y = tt[y];
        }
        sol += fmin;
        }
    }
    out << sol;
    return 0;
}