Menu
Article ACM

POJ 1149 PIGS

NodeKey

NodeKey

• 4 min read

本来在学校新搞的vj上挂了一套网络流的题打算大刷特刷，突然发现还有两天就考毛概了……然而我又一点也没看……不得不先把它放下。

是昨天考完开始看这题的……想了大概3个小时，否定了很多想法，然后就没去想了……因为据说是比较经典的构图题，本来还想自己想出来的，结果今天还是没办法去看了题解，顺便发现了个好东西。
网络流建模汇总

不得不说这道题的构图思路真是巧妙，而且我自己的想法与题解的想法真的已经十分接近了……
十分建议在看题解之前好好思考构图。

题意：
有n个人买猪，总共有m个猪圈，每个人只能去特定的猪圈买猪，按照给定顺序买，在每次购买之后管理员都可以自由调整这位顾客所能购买的猪圈里的剩下的猪，以便使得卖出的猪最多。问最多能卖多少。

思路：
先放可行思路

  • 每个顾客分别用一个结点来表示。
  • 对于每个猪圈的第一个顾客,从源点向他连一条边,容量就是该猪圈里的猪的初始数量。如果从源点到一名顾客有多条边,则可以把它们合并成一条,容量相加。
  • 对于每个猪圈,假设有 n 个顾客打开过它,则对所有整数 i∈[1, n),从该猪圈的第 i 个顾客向第 i + 1 个顾客连一条边,容量为 inf 。
  • 从各个顾客到汇点各有一条边,容量是各个顾客能买的数量上限。

如果是思考良久的你理解了这个构图法一定会拍手称快，我这里简单解释一下
构图最巧妙的地方在于顾客之间的流量，对于两个顾客，如果他们的起始可买猪圈集合有交集，那么他们最终实际可购买集合就是两个集合的并集，因此流量设为 inf 。
至于猪圈的省略缩点，也可以算是巧妙，但一般都想得到，就不解释了。

详细的构图思路见上述文档。

而我的不可行思路则是源点与汇点反过来，以人的购买需求为流量，想要在猪之间构建边，一直得不到正解……

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>

using namespace std;
const int maxn = 310;
const int inf = 0x3f3f3f3f;

int n, m, st, en;
int dis[maxn][maxn];
int flow[maxn][maxn];
int level[maxn], cur[maxn], que[maxn * maxn];
vector<int> vec[maxn * 10];
int val[maxn];

bool bfs()
{
    memset(level, -1, sizeof level);
    que[0] = st;
    level[st] = 0;
    int l = 0, r = 1, u;
    while (l < r) {
        u = que[l++];
        for (int i = 0; i <= en; i++)
            if (flow[u][i] && level[i] == -1) {
                level[i] = level[u] + 1;
                que[r++] = i;
            }
    }
    return level[en] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == en)
        return low;
    for (int& i = cur[u]; i <= en; i++) {
        if (flow[u][i] > 0 && level[i] == level[u] + 1
            && (cflow = dfs(i, min(low, flow[u][i])))) {
            flow[u][i] -= cflow;
            flow[i][u] += cflow;
            return cflow;
        }
    }
    return 0;
}

int dinic()
{
    int ans = 0, cflow;
    while (bfs()) {
        memset(cur, 0, sizeof cur);
        while ((cflow = dfs(st, inf)))
            ans += cflow;
    }
    return ans;
}

int main()
{
    int f, num, pighouse;
    while (scanf("%d %d", &m, &n) != EOF) {
        st = 0, en = n + 1;
        memset(flow, 0, sizeof flow);
        for (int i = 1; i <= m; i++)
            scanf("%d", val + i);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &num);
            for (int j = 0; j < num; j++) {
                scanf("%d", &pighouse);
                vec[pighouse].push_back(i);
            }
            scanf("%d", &f);
            flow[i][en] = f;
        }
        for (int i = 1; i <= m; i++) {
            int pre = vec[i][0], sz = vec[i].size(), cur;
            flow[st][pre] += val[i];
            for (int j = 1; j < sz; j++) {
                cur = vec[i][j];
                flow[pre][cur] = inf;
                pre = cur;
            }
        }
        printf("%d\n", dinic());
    }
    return 0;
}
Share