LIGHT - Hệ thống đèn

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>
const int N = 300;
const int oo = trunc(1e9);
using namespace std;
int c[N][N], f[N][N];
int Q[N], T[N], cx[N], cy[N];
int m, n, k, s = 0, t;
vector<int> a[N];

bool FindPath() {
    int l = 1, r = 1, i, u, v;
    Q[1] = s;
    for(i=1; i<=t; i++) T[i] = -1;
    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 == t) return true;
            }
        }
    }
    return false;
}

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

int main()
{
    scanf("%d %d %d\n", &m, &n, &k);
    int i; t = m + n + 1;
    for(i=1; i<=m; i++)
        scanf("%d", &cx[i]);
    for(i=1; i<=n; i++)
        scanf("%d", &cy[i]);

    int x, y;
    for(i=1; i<=k; i++) {
        scanf("%d %d", &x, &y);
        c[x][m + y] = oo;
        a[x].push_back(m + y);
        a[m + y].push_back(x);
        if (c[s][x] == 0) {
            c[s][x] = cx[x];
            a[s].push_back(x);
        }
        if (c[m + y][t] == 0) {
            c[m + y][t] = cy[y];
            a[m + y].push_back(t);
        }
    }
    while (FindPath())
        IncFlow();
    int res = 0;
    for(i=1; i<=m; i++) res += f[s][i];
    printf("%d", res);
    return 0;
}

Download