POJ3081 网络流

发表于 分类于

常见的多限制匹配问题，每头牛需要选择一种食物和一种饮料，每种食物和饮料只能被一头牛选到，所以直接建图，分三部分，左边为所有的食物，和源连边，容量为 11，右边是饮料，和汇连边，容量为 11，为了达到每头牛都只能选择一种食物和饮料的目的，中间为牛，每头牛拆成两个点，两个点连边，容量为 11，点 11 和食物连，点 22 和饮料连，在这基础上直接跑最大流即可。

我的代码：

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
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;
const int MAX = 402;
const int oo = 0x3f3f3f3f;
struct Edge {
  int num, ne, cap;
} e[MAX * MAX];
int pre[MAX], pree[MAX], low[MAX], p[MAX];
int gap[MAX], cur[MAX], dist[MAX];
int n, st, ed, K;

int get() {
  char ch;
  bool flag = false;
  int ret = 0;
  while ((ch = getchar()) < '0' || ch > '9')
    if (ch == '-') break;
  if (ch == '-')
    flag = true;
  else
    ret = ch - '0';
  while ((ch = getchar()) >= '0' && ch <= '9') ret = ret * 10 + ch - '0';
  return ret;
}

int sap() {
  int ret = 0;
  bool done;
  memset(gap, 0, sizeof(gap));
  memset(dist, 0, sizeof(dist));
  memset(low, 0, sizeof(low));
  for (int i = 0; i < n; i++) {
    cur[i] = p[i];
  }
  gap[0] = n;
  low[st] = oo;
  int u = st;
  while (dist[st] < n) {
    done = true;
    for (int i = cur[u]; ~i; i = e[i].ne) {
      int v = e[i].num;
      cur[u] = i;
      if (e[i].cap && dist[u] == dist[v] + 1) {
        pre[v] = u;
        pree[v] = i;
        low[v] = min(low[u], e[i].cap);
        u = v;
        if (u == ed) {
          do {
            e[pree[u]].cap -= low[ed];
            e[pree[u] ^ 1].cap += low[ed];
            u = pre[u];
          } while (u != st);
          ret += low[ed];
        }
        done = false;
        break;
      }
    }
    if (done) {
      gap[dist[u]]--;
      if (!gap[dist[u]]) return ret;
      dist[u] = n;
      for (int i = p[u]; ~i; i = e[i].ne) {
        if (e[i].cap) {
          dist[u] = min(dist[u], dist[e[i].num] + 1);
        }
      }
      gap[dist[u]]++;
      cur[u] = p[u];
      if (u != st) u = pre[u];
    }
  }
  return ret;
}

void add(const int& u, const int& v, const int& cap) {
  e[K].num = v;
  e[K].cap = cap;
  e[K].ne = p[u];
  p[u] = K++;
  e[K].num = u;
  e[K].cap = 0;
  e[K].ne = p[v];
  p[v] = K++;
}

int main() {
  int np, f, d;
  int m1, m2, x;
  while (~scanf("%d%d%d", &np, &f, &d)) {
    n = 2 * np + f + d + 2;
    st = 0;
    ed = n - 1;
    for (int i = 0; i < n; i++) p[i] = -1;
    K = 0;
    for (int i = 1; i <= f; i++) {
      add(st, i, 1);
    }
    for (int i = 1; i <= d; i++) {
      add(i + 2 * np + f, ed, 1);
    }
    for (int i = 1; i <= np; i++) {
      add(i + f, i + np + f, 1);
    }
    for (int i = 1; i <= np; i++) {
      m1 = get();
      m2 = get();
      while (m1--) {
        x = get();
        add(x, i + f, 1);
      }
      while (m2--) {
        x = get();
        add(i + f + np, x + f + 2 * np, 1);
      }
    }
    printf("%d\n", sap());
  }
  return 0;
}