SP4063 MPIGS - Sell Pigs / P4638 [SHOI2011] 银行家题解

SunnyYuan的博客 / 2024-07-15 / 原文

考虑使用网络流。

建立源点 $S$ 和汇点 $T$。

每个人作为一个点，将它们与汇点 $T$ 连接，权值为需要的猪的数量。

然后对于每个人，如果和之前的某个人开了相同的猪圈，那么就将之前的那个人的点与这个人的点连接。

如果猪圈还没有被开过，就从源点 $S$ 连接这个点，权值为猪圈猪的初始数量。

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 2510, M = 1000010, INF = 0x3f3f3f3f3f3f3f3f;

struct edge {
    int to, next, w;
} e[M];

int head[N], idx = 1;

void add(int u, int v, int w) {
    idx++, e[idx].to = v, e[idx].next = head[u], e[idx].w = w, head[u] = idx;
    idx++, e[idx].to = u, e[idx].next = head[v], e[idx].w = 0, head[v] = idx;
}

int n, m, S, T;
int dep[N];

bool bfs() {
    queue<int> q;
    q.push(S);
    memset(dep, 0x3f, sizeof(dep));
    dep[S] = 1;
    while (q.size()) {
        int t = q.front();
        q.pop();

        for (int i = head[t]; i; i = e[i].next) {
            int to = e[i].to;
            if (dep[to] > dep[t] + 1 && e[i].w) {
                dep[to] = dep[t] + 1;
                q.push(to);
            }
        }
    }
    if (dep[T] < INF) return true;
    else return false;
}

int dinic(int u, int limit) {
    if (u == T) return limit; 
    int rest = limit;
    for (int i = head[u]; i && rest; i = e[i].next) {
        int to = e[i].to;
        if (dep[to] == dep[u] + 1 && e[i].w) {
            int k = dinic(to, min(rest, e[i].w));
            if (!k) dep[to] = INF;
            rest -= k;
            e[i].w -= k;
            e[i ^ 1].w += k;
        }
    }
    return limit - rest;
}

int last[N], init[N];

signed main() {
    freopen("a.in", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> n;

    for (int i = 1; i <= m; i++) cin >> init[i];
    S = 0, T = n + 1;
    for (int i = 1; i <= n; i++) {
        int cnt;
        cin >> cnt;
        while (cnt--) {
            int x;
            cin >> x;
            if (last[x]) add(last[x], i, INF);
            else add(S, i, init[x]);
            last[x] = i;
        }
        int x;
        cin >> x;
        add(i, T, x);
    }

    int flow = 0, maxflow = 0;
    while (bfs()) while (flow = dinic(S, INF)) maxflow += flow;
    cout << maxflow << '\n';
    return 0;
}