uva 12168（二分图最大匹配--最大独立集）

 1 /**************************************************
 2  * Author     : xiaohao Z
 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
 4  * Last modified : 2014-02-25 22:13
 5  * Filename     : uva_12168.cpp
 6  * Description     : 
 7  * ************************************************/
 8 
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <cstdlib>
13 #include <cmath>
14 #include <algorithm>
15 #include <queue>
16 #include <stack>
17 #include <vector>
18 #include <set>
19 #include <map>
20 #define MP(a, b) make_pair(a, b)
21 #define PB(a) push_back(a)
22 
23 using namespace std;
24 typedef long long ll;
25 typedef pair<int, int> pii;
26 typedef pair<unsigned int,unsigned int> puu;
27 typedef pair<int, double> pid;
28 typedef pair<ll, int> pli;
29 typedef pair<int, ll> pil;
30 
31 const int INF = 0x3f3f3f3f;
32 const double eps = 1E-6;
33 const int LEN = 1002;
34 int Map[LEN][LEN], n, c, d;
35 int p[LEN][2], vis[LEN], link[LEN];
36 
37 bool dfs(int u){
38     for(int i=0; i<n; i++){
39         if(Map[u][i] && !vis[i]){
40             vis[i] = 1;
41             if(link[i] == -1 || dfs(link[i])){
42                 link[i] = u;
43                 return true;
44             }
45         }
46     }
47     return false;
48 }
49 
50 int hungary(){
51     int ret = 0;
52     memset(link, -1, sizeof link);
53     for(int i=0; i<n; i++){
54         memset(vis, 0, sizeof vis);
55         if(dfs(i)) ret ++ ;
56     }
57     return ret;
58 }
59 
60 int main()
61 {
62 //    freopen("in.txt", "r", stdin);
63 
64     ios::sync_with_stdio(false); 
65     int T, num;
66     char an;
67     cin >> T;
68     while(T--){
69         cin >> c >> d >> n;
70         memset(Map, 0, sizeof Map);
71         for(int i=0; i<n; i++){
72             cin >> an >> num;num--;
73             if(an == ‘D‘) num += c;
74             p[i][0] = num;
75             cin >> an >> num; num--;
76             if(an == ‘D‘) num += c;
77             p[i][1] = num;
78         }
79         for(int i=0; i<n; i++)
80             for(int j=0; j<n; j++){
81                 if(i == j) continue;
82                 if(p[i][1] == p[j][0] || p[j][1] == p[i][0]){
83                     Map[i][j] = 1;
84                 }
85             }
86         int ans = hungary();
87         printf("%d\n", (2*n - ans)/2);
88     }
89     return 0;
90 }