hihoCoder#1127 二分图三·二分图最小点覆盖和最大独立集

主要是介绍了两个定理：

1. 二分图最大匹配数 = 二分图最小点覆盖数

2. 二分图最小点覆盖数 = 二分图顶点数 - 二分图最小点覆盖数

注意，都是二分图

代码：（匈牙利算法）

 1 #include <iostream>
 2 #include <cstring>
 3 
 4 using namespace std;
 5 
 6 #define MAX_N 1024
 7 #define MAX_M 16384
 8 
 9 int N, M;
10 int f[MAX_N];
11 int n[MAX_M];
12 int u[MAX_M];
13 int v[MAX_M];
14 int m[MAX_N];
15 bool c[MAX_N];
16 
17 bool find(int p) {
18   for (int i = f[p]; i != 0; i = n[i]) {
19     if (c[v[i]])
20       continue;
21     c[v[i]] = true;
22     if (!m[v[i]] || find(m[v[i]])) {
23       m[p] = v[i];
24       m[v[i]] = p;
25       return true;
26     }
27   }
28   return false;
29 }
30 
31 int solve() {
32   int res = 0;
33   for (int i = 1; i <= N; i++) {
34     memset(c, 0, sizeof(c));
35     if (!m[i] && find(i))
36       res++;
37   }
38   return res;
39 }
40 
41 int main() {
42 
43   memset(c, 0, sizeof(c));
44   memset(m, 0, sizeof(m));
45 
46   scanf("%d%d", &N, &M);
47   for (int i = 0, j = 0; i < M; i++) {
48     int a, b;
49     scanf("%d%d", &a, &b);
50     j++;
51     u[j] = a;
52     v[j] = b;
53     n[j] = f[a];
54     f[a] = j;
55     j++;
56     u[j] = b;
57     v[j] = a;
58     n[j] = f[b];
59     f[b] = j;
60   }
61 
62   int x = solve();
63   printf("%d
%d
", x, N - x);
64 
65   return 0;
66 }