猪问题

解题思路

本题是一个卖猪最大化的问题，每次将顾客打开的猪舍中挑一些猪卖给顾客，同时还能将这些猪舍内的猪重新分配，然后要求能买的最大数量。

如果每次不能重新分配，那么这就是一个经典的二分图求最大匹配的问题。从每个源点向猪舍连一条边，容量为最开始该猪舍中猪的数量。嘲弄从每个顾客向汇点连一条边，容量为他要买的猪的数量。对于每个顾客，从他拥有钥匙的猪舍向他连一条容量为 $+\infty$ 的边。

但是现在还有一个难点，我们该如何处理重新分配这个限制。假设在当前顾客之前有一个顾客开的猪舍和当前顾客开的猪舍有公共猪舍，那么当前顾客就可能从别的猪舍中拿到猪，猪的来源会变多，我们需要考虑如何将这个来源建到图中。

假设当前顾客能打开一些猪舍，现在这些猪舍里的猪可以重新分配，我们该如何表示出来这个重新分配呢。其实可以看成是这个顾客先将所有猪拿到手里，再重新分配到这些猪舍中。所有我们可以从这个顾客向他能开的猪舍连一条容量是 $+\infty$ 的边，这样就能体现重新分配这一点。

但是通过以上的方式建图之后，我们还失去了一个重要的点，先去了时序这个概念，这样就没有一个先来后到的顺序，而变成了所有顾客同时到来，这样就不对了。

那我们如何能够在满足之前的转移的前提下，还能体现时序这个概念呢，可以发现，每个顾客只能从前面的顾客分配的结果中进行他的操作。那我们能不能将顾客向猪的连边换掉，换成顾客向顾客之间连边，并且只从先到的顾客向后到的顾客连边，这样就能体现时序这个概念。

对于当前顾客，首先是一些他能打开的猪舍，这些猪舍有哪些情况呢，一种是没有被之前的顾客打开过的猪舍，被当前顾客第一次打开，这种情况我们可以直接从源点向当前顾客连一条容量是该猪舍初始猪的数量的边；另一种情况是这个猪舍已经被前面的顾客打开过了，那么这个猪舍里面猪的来源就不那么纯粹了，他要么是前面某个顾客挑剩下的，要么是能流向前面某个顾客的所有猪中的一部分。可以发现不管是哪种情况，都一定经过了前面某个顾客之手，这种猪舍我们直接从前面某个顾客向当前顾客连边就可以了，由于重新分配的数量没有任何限制，所以前面某个顾客给当前顾客留下的遗产可以是无穷大的，所以这种边的容量应该设为 $+\infty$。注意每个顾客仍然要向汇点连边。

通过以上的方式重新建图，新图体现了重新分配还保证了时序，且新图的可行流和原题的可行解一一对应，因此直接在新图中求最大流即可。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110, M = 20210, INF = 0x3f3f3f3f;

int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx; //邻接表
int q[N], d[N], cur[N]; //队列、层数、当前弧
int pig[1010]; //记录每个猪舍猪的数量
int last[1010]; //记录每个猪舍最近一次打开的人是谁

void add(int a, int b, int c) //添加边
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

bool bfs() //建立分层图，判断是否存在增广路径
{
    int hh = 0, tt = 0;
    q[0] = S;

    memset(d, 0, sizeof d);
    d[S] = 1;

    cur[S] = h[S];

    while(hh <= tt)
    {
        int t = q[hh++];

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];

            if(!d[j] && w[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];

                if(j == T) return true;

                q[++tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int flow) //统计从 u 往终点能传输的最大流量，上限为 flow
{
    if(u == T) return flow;

    int rest = flow;
    for(int i = cur[u]; i != -1 && rest; i = ne[i])
    {
        cur[u] = i;

        int j = e[i];
        if(d[j] == d[u] + 1 && w[i])
        {
            int k = find(j, min(w[i], rest));
            if(!k) d[j] = 0;

            w[i] -= k;
            w[i ^ 1] += k;
            rest -= k;
        }
    }
    return flow - rest;
}

int dinic() //求最大流
{
    int maxf = 0, flow;
    while(bfs())
        while(flow = find(S, INF)) maxf += flow;
    return maxf;
}

int main()
{
    scanf("%d%d", &m, &n);

    memset(h, -1, sizeof h); //初始化邻接表

    for(int i = 1; i <= m; i++) scanf("%d", &pig[i]);

    S = 0, T = n + 1; //源点、汇点
    for(int i = 1; i <= n; i++)
    {
        int a, b;
        scanf("%d", &a);
        while(a--)
        {
            int k;
            scanf("%d", &k);
            if(!last[k]) add(S, i, pig[k]); //如果这个猪舍第一次打开，从源点向当前顾客连一条边，容量为这个猪舍起始猪的数量
            else add(last[k], i, INF); //否则从最近一个打开这个猪舍的人向当前顾客连一条边，容量为 INF
            last[k] = i; //更新这个猪舍最近一个打开的人
        }
        scanf("%d", &b);
        add(i, T, b); //从当前顾客向汇点连一条边，容量为该顾客要买的猪的数量
    }
    printf("%d\n", dinic());

    return 0;
}