uva11419 二分图--最小覆盖=最大匹配

大白书355
 1 // UVa11419 SAM I AM
 2 // Rujia Liu
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <vector>
 6 #include <algorithm>
 7 using namespace std;
 8 
 9 const int maxn = 1000 + 5; // 单侧顶点的最大数目
10 
11 // 二分图最大基数匹配
12 struct BPM {
13   int n, m;               // 左右顶点个数
14   vector<int> G[maxn];    // 邻接表
15   int left[maxn];         // left[i]为右边第i个点的匹配点编号，-1表示不存在
16   bool T[maxn];           // T[i]为右边第i个点是否已标记
17 
18   int right[maxn];        // 求最小覆盖用
19   bool S[maxn];           // 求最小覆盖用
20 
21   void init(int n, int m) {
22     this->n = n;
23     this->m = m;
24     for(int i = 0; i < n; i++) G[i].clear();
25   }
26 
27   void AddEdge(int u, int v) {
28     G[u].push_back(v);
29   }
30 
31   bool match(int u){
32     S[u] = true;
33     for(int i = 0; i < G[u].size(); i++) {
34       int v = G[u][i];
35       if (!T[v]){
36         T[v] = true;
37         if (left[v] == -1 || match(left[v])){
38           left[v] = u;
39           right[u] = v;
40           return true;
41         }
42       }
43     }
44     return false;
45   }
46 
47   // 求最大匹配
48   int solve() {
49     memset(left, -1, sizeof(left));
50     memset(right, -1, sizeof(right));
51     int ans = 0;
52     for(int u = 0; u < n; u++) { // 从左边结点u开始增广
53       memset(S, 0, sizeof(S));
54       memset(T, 0, sizeof(T));
55       if(match(u)) ans++;
56     }
57     return ans;
58   }
59 
60   // 求最小覆盖。X和Y为最小覆盖中的点集
61   int mincover(vector<int>& X, vector<int>& Y) {
62     int ans = solve();
63     memset(S, 0, sizeof(S));
64     memset(T, 0, sizeof(T));
65     for(int u = 0; u < n; u++)
66       if(right[u] == -1) match(u); // 从所有X未盖点出发增广 如果他没有找到匹配对象说明X方向的小于Y方向的，显然Y的个数才是此时的最小匹配
67     for(int u = 0; u < n; u++)
68       if(!S[u]) X.push_back(u); // X中的未标记点
69     for(int v = 0; v < m; v++)
70       if(T[v]) Y.push_back(v);  // Y中的已标记点
71    return ans;
72   }
73 };
74 
75 BPM solver;
76 
77 int R, C, N;
78 
79 int main(){
80   int kase = 0;
81   while(scanf("%d%d%d", &R, &C, &N) == 3 && R && C && N) {
82     solver.init(R, C);
83     for(int i = 0; i < N; i++) {
84       int r, c;
85       scanf("%d%d", &r, &c); r--; c--;
86       solver.AddEdge(r, c);
87     }
88     vector<int> X, Y;
89     int ans = solver.mincover(X, Y);
90     printf("%d", ans);
91     for(int i = 0; i < X.size(); i++) printf(" r%d", X[i]+1);
92     for(int i = 0; i < Y.size(); i++) printf(" c%d", Y[i]+1);
93     printf("
");
94   }
95   return 0;
96 }