POJ 3281 Dining(最大流最小割)

Description

农夫为他的 N (1 ≤ N ≤ 100) 牛准备了 F (1 ≤ F ≤ 100)种食物和 D (1 ≤ D ≤ 100) 种饮料。每头牛都有各自喜欢的食物和饮料，而每种食物或饮料只能分配给一头牛。最多能有多少头牛可以同时得到喜欢的食物和饮料？

Analyze

不可以二分图匹配，因为牛要匹配两种东西，求其跟每种东西的最大匹配，取交集也不是，取并集也不是，需建模用最大流解决

多源点、多汇点要建立超源点、超汇点

牛置于中间，左放食物右放饮料（或反过来）

连线权值为1，求最大流即答案

要注意：中间的牛要拆点

关于拆点

很明显,一头牛同时匹配了多种食物饮料,最大流是2,但答案是1(只满足了一头牛)

限流：限制流经每头牛的流量最大为1

Code

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <bitset>
#include <string>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define eps 1e-8
#define PI acos(-1.0)
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
#define Close ios::sync_with_stdio(false);

void Debug(char * s)
{
    cout << "-------------  " << s << "  -------------" << '\n';
}
const int N = 1005;

int n;///网络流中最重要的是建模构图，其中全局变量总点数n要计算清楚
int maxflow, deep[N];

struct edge
{
    int from, to, w, pre;
} a[N * N];

queue<int> q;
int cnt = -1;
int head[N], cur[N];

void add(int from, int to, int w)
{
    a[++cnt].to = to;
    a[cnt].from = from;
    a[cnt].pre = head[from];
    a[cnt].w = w;
    head[from] = cnt;
}

bool bfs(int s, int t)
{
    memset(deep, INF, sizeof(deep));
    while(!q.empty())
        q.pop();
    for(int i = 0; i <= n; ++i)
        cur[i] = head[i];
    deep[s] = 0;
    q.push(s);

    while(!q.empty())
    {
        int first = q.front();
        q.pop();
        for(int i = head[first]; ~i; i = a[i].pre)
        {
            if(deep[ a[i].to ] == INF && a[i].w)///w在此处用来做标记 是正图还是返图
            {
                deep[ a[i].to ] = deep[first] + 1;
                q.push(a[i].to);
            }
        }
    }
    if(deep[t] < INF)
        return 1;
    return 0;
}

int dfs(int now, int t, int limit)
{
    if(!limit || now == t)
        return limit;
    int flow = 0, f;
    for(int i = cur[now]; ~i; i = a[i].pre)
    {
        cur[now] = i;
        if(deep[ a[i].to ] == deep[now] + 1)
            if(f = dfs(a[i].to, t, min(limit, a[i].w)))
            {
                flow += f;
                limit -= f;
                a[i].w -= f;
                a[i ^ 1].w += f;
                if(!limit)
                    break;
            }
    }
    return flow;
}

///bfs分层，dfs增广、处理残余网络、反向边

void Dinic(int s, int t)
{
    int temp;
    while(bfs(s, t))
    {
        while((temp = dfs(s, t, INF)) > 0)
            maxflow += temp;
    }
}

int main()
{
    memset(head, -1, sizeof(head));
    int nn, ff, dd;
    scanf("%d%d%d", &nn, &ff, &dd);
    n = 2 * nn + ff + dd + 2;
    for(int i = 1; i <= ff; ++i)
    {
        add(0, i, 1);
        add(i, 0, 0);
    }
    for(int i = 1; i <= dd; ++i)
    {
        add(i + 2 * nn + ff, 1 + dd + 2 * nn + ff, 1);
        add(1 + dd + 2 * nn + ff, i + 2 * nn + ff, 0);
    }
    int num_f = 0, num_d = 0, idx = 0;
    for(int i = 1; i <= nn; ++i)
    {
        scanf("%d%d", &num_f, &num_d);
        for(int j = 1; j <= num_f; ++j)
        {
            scanf("%d", &idx);
            add(idx, i + ff, 1);
            add(i + ff, idx, 0);
        }
        for(int j = 1; j <= num_d; ++j)
        {
            scanf("%d", &idx);
            add(i + nn + ff, idx + 2 * nn + ff, 1);
            add(idx + 2 * nn + ff, i + nn + ff, 0);
        }
        add(i + ff, i + nn + ff, 1);
        add(i + nn + ff, i + ff, 0);
    }
    Dinic(0, 1 + dd + 2 * nn + ff);
    cout << maxflow << '\n';
    return 0;
}
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

n（总点数）的计算出错了

添边时超级源点0写成了1

i为序号写成了idx(idx在其他地方做过序号)

所以要分清“同类”