poj 3281 Dining 拆点 最大流

题目链接

题意

有\(N\)头牛，\(F\)个食物和\(D\)个饮料。每头牛都有自己偏好的食物和饮料列表。

问该如何分配食物和饮料，使得尽量多的牛能够既获得自己喜欢的食物又获得自己喜欢的饮料。

建图

1. 在 源点 到 食物 之间加边，边权为\(1\)

2. 在 饮料 到 汇点 之间加边，边权为\(1\)

3. 将牛拆成两点，在两点之间加边，边权为\(1\)

    	这一点很重要，可以从以下两个方面去考虑：
   
    	1) 从含义上，只要流为1，这头牛就被满足了，多了就纯属是浪费。
   
    	2) 从操作上，最后答案是根据最大流的值来判断的，被满足的牛的数目即最大流的值。这一个判断是建立在这样一个事实上的：默认经过每头牛的流为1。因此需要拆点在中间加上限制。
   
    	（其实第一点考虑中所说的“浪费”还是有些含糊其辞的，最合理的考虑还是第二点）
   
   

4. 在 食物 到 喜欢它的牛(1) 之间连边，边权为\(1\)

5. 在 喜欢它的牛(2) 到 饮料 之间连边，边权为\(1\)

Code

#include <cstdio>

#include <cstring>

#include <queue>

#include <iostream>

#define maxn 100010

#define inf 0x3f3f3f3f

using namespace std;

typedef long long LL;

struct Edge { int to, ne, c; }edge[maxn];

int dep[maxn], ne[maxn], n,f,d, tot, s,t;

void add(int u, int v, int c) {

    edge[tot] = {v, ne[u], c};

    ne[u] = tot++;

    edge[tot] = {u, ne[v], 0};

    ne[v] = tot++;

}

int bfs(int src) {

    memset(dep, 0, sizeof dep);

    dep[src] = 1;

    queue<int> q;

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

    q.push(src);

    while (!q.empty()) {

        int u = q.front(); q.pop();

        for (int i = ne[u]; ~i; i = edge[i].ne) {

            int v = edge[i].to;

            if (edge[i].c > 0 && !dep[v]) dep[v] = dep[u] + 1, q.push(v);

        }

    }

    return dep[t];

}

int dfs(int u, int flow) {

    if (u == t) return flow;

    int ret = 0;

    for (int i = ne[u]; ~i; i = edge[i].ne) {

        int v = edge[i].to;

        if (edge[i].c > 0 && dep[v] == dep[u] + 1) {

            int c = dfs(v, min(flow-ret, edge[i].c));

            edge[i].c -= c;

            edge[i^1].c += c;

            ret += c;

            if (ret == flow) break;

        }

    }

    if (!flow) dep[u] = 0;

    return ret;

}

int main() {

    while (scanf("%d%d%d", &n, &f, &d) != EOF) {

        s = 0, t = f+2*n+d+1;

        tot = 0; memset(ne, -1, sizeof ne);

        for (int i = 1; i <= f; ++i) add(s, i, 1);

        for (int i = 1; i <= d; ++i) add(f+2*n+i, t, 1);

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

            int a,b,x;

            add(f+i, f+n+i, 1);

            scanf("%d%d", &a, &b);

            while (a--) {

                scanf("%d", &x);

                add(x, f+i, 1);

            }

            while (b--) {

                scanf("%d", &x);

                add(f+n+i, f+2*n+x, 1);

            }

        }

        int ans=0, tmp;

        while (bfs(s)) {

            while (tmp = dfs(s, inf)) ans += tmp;

        }

        printf("%d\n", ans);

    }

    return 0;

}