Crimiville

Problem

You are given a bipartite graph G=(X∪Y, E)$G=(X\cup Y, E)$. Is there a S ⊆ X $S\subseteq X$ such that |Γ(S)| < |S|$\lvert\Gamma(S)\rvert\lt\lvert S\rvert$? If not, maximize ∑_i∈Sw(i) − ∑_i∈Γ(S)w(i) $\sum_{i\in S}w(i)-\sum_{i\in\Gamma(S)}w(i)$ subject to |Γ(S)| = |S|$\lvert\Gamma(S)\rvert=\lvert S\rvert$.

Solution

As a direct consequences of Hall's theorem, we just have to check if there is a perfect matching to answer the first question.

The "subject to" part of the second question is annoying. We can add a sufficiently large number to each weight, so any infeasible solution won't be the maximum.

Finally, with max(∑_i∈Sw(i) − ∑_i∈Γ(S)w(i)) = ∑_i∈Xw(i) − min(∑_i∈Γ(S)w(i) + ∑_i∈X\Sw(i)) $$\max\left(\sum_{i\in S}w(i)-\sum_{i\in\Gamma(S)}w(i)\right)=\sum_{i\in X}w(i)-\min\left(\sum_{i\in\Gamma(S)}w(i)+\sum_{i\in X\setminus S}w(i)\right)$$ we can get the answer after computing the min-cut of a graph similar to the original one.

Source Code

#include <cstdio>
#include <list>
#include <numeric>
using namespace std;
constexpr int maxn = 200 * 2 + 2;
int c[maxn][maxn], f[maxn][maxn], e[maxn], h[maxn];
void push(int u, int v) {
    int x = min(c[u][v] - f[u][v], e[u]);
    if(x) {
        f[u][v] += x;
        f[v][u] -= x;
        e[u] -= x;
        e[v] += x;
    }
}
void relabel(int u, int n) {
    h[u] = 2 * n;
    for(int i = 0; i < n; i++)
        if(c[u][i] > f[u][i])
            h[u] = min(h[u], h[i] + 1);
}
void discharge(int u, int n) {
    while(e[u]) {
        for(int i = 0; i < n && e[u]; i++)
            if(h[u] == h[i] + 1)
                push(u, i);
        if(e[u])
            relabel(u, n);
    }
}
int max_flow(int s, int t, int n) {
    for(int i = 0; i < n; i++)
        fill_n(f[i], n, 0);
    for(int i = 0; i < n; i++) {
        f[s][i] = e[i] = c[s][i];
        f[i][s] = -f[s][i];
    }
    fill_n(h, n, 0);
    h[s] = n;
    list<int> q;
    for(int i = 0; i < n; i++)
        if(i != s && i != t)
            q.push_back(i);
    for(auto i = q.begin(); i != q.end(); ++i) {
        int oh = h[*i];
        discharge(*i, n);
        int nh = h[*i];
        if(oh != nh)
            q.splice(q.begin(), q, i);
    }
    return accumulate(f[s], f[s] + n, 0);
}
constexpr int maxda = 10000;
constexpr int large = 200 * maxda + 1;
constexpr int maxc = maxda + large;
void solve() {
    int n;
    scanf("%d", &n);
    int v = 2 * n + 2;
    for(int i = 0; i < v; i++)
        fill_n(c[i], v, 0);
    for(int i = 0; i < n; i++) {
        int k;
        scanf("%d", &k);
        for(int j = 0; j < k; j++) {
            int x;
            scanf("%d", &x);
            c[x][n + i] = 1;
        }
    }
    for(int i = 0; i < n; i++) {
        c[v - 2][i] = 1;
        c[n + i][v - 1] = 1;
    }
    if(max_flow(v - 2, v - 1, v) != n) {
        for(int i = 0; i < 2 * n; i++)
            scanf("%*d");
        puts("need reinforcement.");
        return;
    }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(c[i][n + j])
                c[i][n + j] = maxc;
    for(int i = 0; i < n; i++) {
        int a;
        scanf("%d", &a);
        c[n + i][v - 1] = a + large;
    }
    int sumd = 0;
    for(int i = 0; i < n; i++) {
        int d;
        scanf("%d", &d);
        sumd += c[v - 2][i] = d + large;
    }
    printf("%d\n", sumd - max_flow(v - 2, v - 1, v));
}
int main() {
    int t;
    scanf("%d", &t);
    while(t--)
        solve();
}