hdu 3829 Cat VS Dog

http://acm.hdu.edu.cn/showproblem.php?pid=3829

　　这道题是一道二分匹配。这题虽然猫和狗是对立的，不过却要用小朋友的关系来构图。让我详细的说还真的挺难说的懂，反正就是如果两个小朋友间讨厌的动物是另一个的喜欢的动物，那么这两个小朋友之间就得连上一条边。这里可以理解为两个小朋友间产生了敌对的关系了。为了大家和睦相处，只好消灭足够多的敌对关系了，于是最大匹配的算法就出现了！

　　虽然这次数据规模不大，不过我还是用了hk算法，拿来练习！这次刚打出来的代码反映出我过往打hk算法的一个问题，在dfs前忘记判断这个x点是否已经匹配了！可笑的是，我以前的代码都过了，这次就因为这个问题TLE，应该是进入死循环了，所以我之前的几篇hk算法的代码都修正了这个问题！

然后就是我的代码：(31ms with g++通过)

View Code

  1 #include <cstdlib>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <vector>
  6 
  7 using namespace std;
  8 
  9 const int maxn = 505;
 10 struct person{
 11     char l[10]; // record like animal
 12     char h[10]; // record hate animal
 13 }p[maxn];
 14 vector<int> rel[maxn];
 15 
 16 int mx[maxn], my[maxn];
 17 int rx[maxn], ry[maxn];
 18 int q[maxn << 1], qf, qb;
 19 
 20 bool bfs(int n){
 21     bool ret = false;
 22 
 23     qf = qb = 0;
 24     for (int i = 0; i < n; i++){
 25         rx[i] = ry[i] = 0;
 26         if (mx[i] == -1) q[qb++] = i;
 27     }
 28 
 29     while (qf < qb){
 30         int cur = q[qf++];
 31 #ifndef ONLINE_JUDGE
 32         printf("cur %d\n", cur);
 33 #endif
 34 
 35         for (int i = 0; i < rel[cur].size(); i++){
 36             int t = rel[cur][i];
 37 
 38             if (!ry[t]){
 39                 ry[t] = rx[cur] + 1;
 40                 if (my[t] == -1){
 41                     ret = true;
 42                 }
 43                 else{
 44                     rx[my[t]] = ry[t] + 1;
 45                     q[qb++] = my[t];
 46                 }
 47             }
 48         }
 49     }
 50 
 51     return ret;
 52 }
 53 
 54 bool dfs(int cur){
 55     for (int i = 0; i < rel[cur].size(); i++){
 56         int t = rel[cur][i];
 57 
 58         if (ry[t] == rx[cur] + 1){
 59             ry[t] = 0;
 60             if (my[t] == -1 || dfs(my[t])){
 61                 my[t] = cur;
 62                 mx[cur] = t;
 63 
 64                 return true;
 65             }
 66         }
 67     }
 68     return false;
 69 }
 70 
 71 int hk(int n){
 72     int cnt = 0;
 73 
 74     for (int i = 0; i < n; i++){
 75         mx[i] = my[i] = -1;
 76     }
 77     while (bfs(n)){
 78         for (int i = 0; i < n; i++){
 79             if (mx[i] == -1 && dfs(i)) cnt++;
 80         }
 81     }
 82 
 83     return cnt;
 84 }
 85 
 86 bool deal(){
 87     int n, m, P;
 88 
 89     if (scanf("%d%d%d", &n, &m, &P) == EOF) return false;
 90     for (int i = 0; i < P; i++){
 91         scanf("%s%s", p[i].l,  p[i].h);
 92         rel[i].clear();
 93         for (int j = 0; j < i; j++){
 94             if (!strcmp(p[i].l, p[j].h) || !strcmp(p[i].h, p[j].l)){
 95                 rel[i].push_back(j);
 96                 rel[j].push_back(i);
 97             }
 98         }
 99     }
100     printf("%d\n", P - hk(P) / 2);
101 
102     return true;
103 }
104 
105 int main(){
106 #ifndef ONLINE_JUDGE
107     freopen("in", "r", stdin);
108 #endif
109     while (deal());
110 
111     return 0;
112 }

——written by Lyon