poj1149--PIGS（最大流）

题意：

有m个猪圈 每个猪圈有不同数量的猪 [0, 1000]
有n个顾客 每个顾客需要Bi头猪 有Ai个钥匙 能打开Ai个不同的猪圈
顾客按顺序来买猪 只能买他有钥匙的猪 买完之后 这几个猪圈的猪可以相互转移

很神奇的题，建图简直太神奇~~

建图：

每个顾客和源点的流量为与该顾客的相连的猪圈且该猪圈之前没有与其他顾客相连的猪圈的猪数量和
每个顾客到汇点的流量是该顾客需要猪的数量
每个顾客需要与上一个选相同猪圈的顾客相连 因为猪圈之间可以相互换 不用考虑不同的猪圈

/*****************************************************

Problem: 1149		User: G_lory

Memory: 632K		Time: 16MS

Language: C++		Result: Accepted

*****************************************************/

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

using namespace std;

const int N = 2010;

const int INF = 0x5f5f5f5f;

int flow[N];

int cap[N][N];

int pre[N];

queue<int> q;

int bfs(int src, int des)

{

    while (!q.empty()) q.pop();

    memset(pre, -1, sizeof pre);

    flow[src] = INF;

    pre[src] = -1;

    q.push(src);

    while (!q.empty())

    {

        int idx = q.front();

        q.pop();

        if (idx == des) break;

        for (int i = 0; i <= des; ++i)

        {

            if (pre[i] == -1 && cap[idx][i] > 0)

            {

                pre[i] = idx;

                flow[i] = min(cap[idx][i], flow[idx]);

                q.push(i);

            }

        }

    }

    if (pre[des] == -1) return -1;

    return flow[des];

}

int maxFlow(int src, int des)

{

    int ans = 0;

    int in = 0;

    while ((in = bfs(src, des)) != -1)

    {

        int k = des;

        while (k != src)

        {

            int last = pre[k];

            cap[last][k] -= in;

            cap[k][last] += in;

            k = last;

        }

        ans += in;

    }

    return ans;

}

int pig[N];

int last[N];

int main()

{

    int m, n;

    scanf("%d%d", &m, &n);

    for (int i = 1; i <= m; ++i)

        scanf("%d", &pig[i]);

    int num, a, b;

    for (int i = 1; i <= n; ++i)

    {

        scanf("%d", &num);

        for (int j = 1; j <= num; ++j)

        {

            scanf("%d", &a);

            if (!last[a])

            {

                last[a] = i;

                cap[0][i] += pig[a];

            }

            else

            {

                cap[ last[a] ][i] = INF;

                last[a] = i;

            }

        }

        scanf("%d", &b);

        cap[i][n + 1] = b;

    }

    printf("%d\n", maxFlow(0, n + 1));

    return 0;

}