Cod sursa(job #1428614)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 4 mai 2015 20:13:14
Problema Flux maxim Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include<iostream>
#include<fstream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<iomanip>
#include<bitset>
using namespace std;

const int N = 1100;

int S = 1, D = N;
int n, m, cap[N][N], fl[N][N], p[N];
vector<int> v[N];

bool bf() {
    int i;
    queue<int> q;

    for(i = S; i <= D; ++i)
        p[i] = 0;

    p[S] = S;
    q.push(S);

    while(!q.empty()) {
        int el = q.front();
        q.pop();

        for(vector<int>::iterator it = v[el].begin(); it != v[el].end(); ++it) {

            if(!p[*it] && cap[el][*it] - fl[el][*it] > 0) {

                p[*it] = el;
                q.push(*it);
            }
        }
    }

    return p[D];
}

int flow() {
    int i, j, rez = 0;

    while(bf()) {

        for(j = S; j < D; ++j) if(cap[j][D] - fl[j][D] > 0) {

            int smin = cap[j][D] - fl[j][D];

            for(i = j; i != S; i = p[i])
                smin = min(smin, cap[p[i]][i] - fl[p[i]][i]);

            fl[j][D] += smin;
            fl[D][j] -= smin;

            for(i = j; i != S; i = p[i]) {

                fl[p[i]][i] += smin;
                fl[i][p[i]] -= smin;
            }

            rez += smin;
        }
    }

    return rez;
}

int main() {
    freopen("maxflow.in", "r", stdin);
    freopen("maxflow.out", "w", stdout);

    cin >> n >> m;
    D = n;

    for(int i = 1; i <= m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;

        cap[a][b] += c;

        v[a].push_back(b);
        v[b].push_back(a);
    }

    cout << flow();

    return 0;
}