POJ3281 (Dining)[网络流]

发表于 | 更新于 | | 阅读次数：

题目链接：http://poj.org/problem?id=3281

这题第一眼看上去有点像二分图匹配，奶牛和他们所喜欢的食物饮料匹配，但是这题的食物和饮料作为两种限制条件不好处理。一种用网络流的建图方式是从超级源点向食物连边，从饮料向超级汇点连边，奶牛放在中间，这样一条可行流就是超级源->食物->奶牛->饮料->超级汇，从而保证了每种食物和饮料都各自只能占用一次，奶牛一次只能占用一种食物和一种饮料，因此我们把每头奶牛拆成一个容量为1的边即可。

这样这种有两个限制条件的匹配图，就可以通过把待匹配项放到图两边的方式来解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int inf=0x3fffffff,N=11000,M=410000;
int d[N],head[M],e[M],next[M],ver[M];
int s,t,m,n,tot=1,maxflow=0;
void add(int u,int v,int w) {
    ver[++tot]=v;e[tot]=w;next[tot]=head[u];head[u]=tot;
    ver[++tot]=u;e[tot]=0;next[tot]=head[v];head[v]=tot;
}
bool bfs() {
    queue<int> q;
    memset(d,0,sizeof(d));
    q.push(s); d[s]=1;
    while(!q.empty()) {
        int x=q.front(); q.pop();
        for(int i=head[x];i;i=next[i]) {
            if(e[i]&&!d[ver[i]]) {
                q.push(ver[i]);
                d[ver[i]]=d[x]+1;
                if(ver[i]==t) return 1;
            }
        }
    }
    return 0;
}
int dinic(int x,int f) {
    int rest=f;
    if(x==t) return f;
    for(int i=head[x];i&&rest;i=next[i]) {
        if(e[i]&&d[ver[i]]==d[x]+1) {
            int now=dinic(ver[i],min(e[i],rest));
            if(!now) d[ver[i]]=0;
            e[i]-=now;
            e[i^1]+=now;
            rest-=now;
        }
    }
    return f-rest;
}
int food[110],drink[110];
int main() {
    int n,F,D,ff,dd;
    scanf("%d%d%d",&n,&F,&D);
    s=0;
    t=F+D+2*n+1;
    for(int i=1;i<=F;i++) add(s,i,1);
    for(int i=1;i<=D;i++) add(F+i,t,1);
    for(int i=1;i<=n;i++) add(F+D+i,F+D+n+i,1);

    for(int i=1;i<=n;i++) {
        scanf("%d%d",&ff,&dd);
        for(int j=1;j<=ff;j++) {
            scanf("%d",food+j);
            add(food[j],F+D+i,1);
        }
        for(int j=1;j<=dd;j++) {
            scanf("%d",drink+j);
            add(F+D+n+i,F+drink[j],1);
        }

    }
    int tmp=0;
    while(bfs())
        while(tmp=dinic(s,inf)) maxflow+=tmp;
    printf("%d",maxflow);
}