完美牛奶（二分图入门）


网络流求二分图最大匹配。

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
/*
Author:ZhouCheng
Date:20090203
*/

#include <stdio.h>

int N, M, S, T, Add, Ans;
char Pan, Mark[520];
int Link[520][520], Fa[520], Now[520];

void Find(int point) {
    if (point != T) {
        Mark[point] = 1;
        int a, b;
        for (a = 1; a <= T; a++)
            if (Link[point][a] > 0 && Mark[a] == 0) {
                if (Link[point][a] >= Now[point] && Now[point] > Now[a]) {
                    Now[a] = Now[point];
                    Fa[a] = point;
                    Find(a);
                } else if (Link[point][a] < Now[point]) {
                    b = Link[point][a];
                    if (b > Now[a]) {
                        Now[a] = b;
                        Fa[a] = point;
                        Find(a);
                    }
                }
            }
        Mark[point] = 0;
    }
}

void Set(int point) {
    if (point != 0) {
        int a, b;
        a = Fa[point];
        b = point;
        Link[a][b] -= Add;
        Link[b][a] += Add;
        Set(a);
    }
}

int main() {
    scanf("%d %d", &N, &M);
    int a, b, c;
    //读入数据，Cow 和 Fence 都处理成点。
    for (a = 1; a <= N; a++) {
        scanf("%d", &b);
        for (; b > 0; b--) {
            scanf("%d", &c);
            Link[a][N + c] = 1000000000;
        }
    }
    //S 源点，T 汇点。
    S = 0;
    T = N + M + 1;
    for (a = 1; a <= N; a++)
        Link[S][a] = 1;
    for (a = N + 1; a < T; a++)
        Link[a][T] = 1;
    //求最大流。
    Pan = 1;
    Ans = 0;
    while (Pan) {
        memset(Fa, 0, sizeof(Fa));
        memset(Now, 0, sizeof(Now));
        for (a = 1, Pan = 0; a <= N; a++)
            if (Link[0][a] > 0 && Link[0][a] > Now[a]) {
                Fa[a] = 0;
                Now[a] = Link[0][a];
                Find(a);
            }
        if (Now[T] != 0) {
            Pan = 1;
            Add = Now[T];
            Set(T);
            Ans += Add;
        }
    }
    //输出结果。
    printf("%d\n", Ans);
    return 0;
}
赏

很惭愧，就做了一点微小的工作

支付宝
微信