题目地址：POJ：1149 — PIGS、OpenJudge百练：OpenJudge – 1149:PIGS

题目描述

Mirko works on a pig farm that consists of M locked pig-houses and Mirko can’t unlock any pighouse because he doesn’t have the keys. Customers come to the farm one after another. Each of them has keys to some pig-houses and wants to buy a certain number of pigs.
All data concerning customers planning to visit the farm on that particular day are available to Mirko early in the morning so that he can make a sales-plan in order to maximize the number of pigs sold.
More precisely, the procedure is as following: the customer arrives, opens all pig-houses to which he has the key, Mirko sells a certain number of pigs from all the unlocked pig-houses to him, and, if Mirko wants, he can redistribute the remaining pigs across the unlocked pig-houses.
An unlimited number of pigs can be placed in every pig-house.
Write a program that will find the maximum number of pigs that he can sell on that day.
有m个猪圈，每个猪圈里初始时有若干头猪。一开始所有猪圈都是关闭的。依次来了n个顾客，每个顾客分别会打开指定的几个猪圈，从中买若干头猪。
每个顾客分别都有他能够买的数量的上限。
每个顾客走后，他打开的那些猪圈中的猪，都可以被任意地调换到其它开着的猪圈里，然后所有猪圈重新关上。
问最多总共能卖出多少头猪。

输入输出格式

输入格式：
The first line of input contains two integers M and N, 1 <= M <= 1000, 1 <= N <= 100, number of pighouses and number of customers. Pig houses are numbered from 1 to M and customers are numbered from 1 to N.
The next line contains M integeres, for each pig-house initial number of pigs. The number of pigs in each pig-house is greater or equal to 0 and less or equal to 1000.
The next N lines contains records about the customers in the following form ( record about the i-th customer is written in the (i+2)-th line):
A K1 K2 … KA B It means that this customer has key to the pig-houses marked with the numbers K1, K2, …, KA (sorted nondecreasingly ) and that he wants to buy B pigs. Numbers A and B can be equal to 0.

输出格式：
The first and only line of the output should contain the number of sold pigs.

输入输出样例

输入样例#1：

3 3
3 1 10
2 1 2 2
2 1 3 3
1 2 6

输出样例#1：

7

题解

我们有一个想法就是根据时间拆点，把每个猪圈拆成n个点，分别代表n个顾客来的时候的状态。最开始的点与源连边，控制这个猪圈内的猪数量。每次顾客要买的猪圈与顾客连边，表示买猪。上一层与下一层猪圈连边，表示继承关系。上一层顾客打开的猪圈两两连边，表示猪的调换。但是我们容易发现这个图的点数O(nm)边数更是O(m^3)，会TLE的。
我们换一种想法，如果有一个顾客想买猪，肯定是从他要买的猪圈的上一个顾客买剩下的猪里买。那么对于每个猪圈，它的猪是从上一个顾客向下一个顾客卖的，因此我们可以对于每个猪圈顾客依次连边。至于猪在不同猪圈的调换，如果下一个顾客的猪圈内部发生调换，容易发现这些猪圈都对应同一个顾客，而顾客点流过的流量代表的是总和，因此猪圈的调换也就不用再管了。这个图的点数O(n)边数O(nm)，瞬间变小了不少。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>

#include <vector>
#include <algorithm>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF 
        : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005, INF = 1e9;

struct Edge {
    int to, cap, nxt;
} gra[MAXN << 1];
int head[MAXN], tot;

inline void addedge(int u, int v, int cap) {
    gra[tot] = Edge {v, cap, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, 0, head[v]}; head[v] = tot++;
}

int level[MAXN];
std::queue<int> que;

inline bool bfs(int s, int t) {
    memset(level, -1, sizeof(level));
    level[s] = 0; que.push(s);
    while(!que.empty()) {
        int u = que.front(); que.pop();
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(gra[i].cap > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                que.push(v);
            }
        }
    }
    return level[t] != -1;
}

int cur[MAXN];
bool vis[MAXN];

inline int dfs(int u, int t, int left) {
    if(u == t || !left) 
        return left;
    int flow = 0; vis[u] = true;
    for(int &i = cur[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(gra[i].cap > 0 && !vis[v] && level[v] == level[u] + 1) {
            int d = dfs(v, t, std::min(left, gra[i].cap));
            if(d > 0) {
                left -= d; flow += d;
                gra[i].cap -= d; gra[i ^ 1].cap += d;
                if(!left) {
                    level[u] = -1;
                    return flow;
                }
            }
        }
    }
    return flow;
}

inline int dinic(int s, int t) {
    int flow = 0;
    while(bfs(s, t)) {
        memset(vis, 0, sizeof(vis));
        memcpy(cur, head, sizeof(head));
        int f;
        while(f = dfs(s, t, INF)) {
            flow += f;
        }
    }
    return flow;
}

int m, n, pnum[MAXN], a, t, S, T;
std::vector<int> list[MAXN];

// 1 ~ n customers

int main() {
    memset(head, -1, sizeof(head));
    m = readint(); n = readint();
    S = n + 1; T = S + 1;
    for(int i = 1; i <= m; i++) {
        pnum[i] = readint();
    }
    for(int i = 1; i <= n; i++) {
        a = readint();
        for(int j = 1; j <= a; j++) {
            t = readint();
            list[t].push_back(i);
        }
        addedge(i, T, readint());
    }
    for(int i = 1; i <= m; i++) {
        if(!list[i].empty()) {
            addedge(S, list[i][0], pnum[i]);
            for(int j = 1; j < list[i].size(); j++) {
                addedge(list[i][j - 1], list[i][j], INF);
            }
        }
    }
    printf("%d", dinic(S, T));
    return 0;
}