BAOVE - Bảo vệ

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>
const int N = 5001;
const int oo = 1000000009;
using namespace std;
int f[N][N], c[N][N], n, Q[N], T[N];
vector<int> a[N];

bool BFS() {
    int l = 1, r = 1, i, u, v;
    Q[1] = n;
    for(i=1; i<=n; i++) T[i] = 0;
    while (l<=r) {
        u = Q[l++];
        for(i=0; i<a[u].size(); i++) {
            v = a[u][i];
            if (T[v] == 0 && c[u][v]>f[u][v]) {
                Q[++r] = v;
                T[v] = u;
                if (v == 1) return true;
            }
        }
    }
    return false;
}

void IncFlow() {
    int v = 1, delta = oo, u;
    while (v != n) {
        u = T[v];
        delta = min(delta, c[u][v] - f[u][v]);
        v = u;
    }
    v = 1;
    while (v != n) {
        u = T[v];
        f[u][v] += delta;
        f[v][u] -= delta;
        v = u;
    }
}

int main()
{
    //freopen("BAOVE.in", "r", stdin);
    scanf("%d\n", &n); int u, v, w;
    while (scanf("%d %d %d\n", &u, &v, &w) == 3) {
        a[u].push_back(v); a[v].push_back(u);
        c[u][v] += w;
    }
    while (BFS()) IncFlow();
    int s = 0;
    for(int i = 0; i<a[n].size(); i++)
        s += f[n][a[n][i]];
    printf("%d", s);
    return 0;
}

Download