嗯...

 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2063

 

这是一道很经典的匈牙利问题：

把男同学看成左边点，女同学看成右边点，如果两个同学愿意同坐过山车，则连边，最后输出最大匹配数即可...

AC代码：

1 #include
      
        2 #include
       
         3 #include
        
          4  5 using namespace std; 6  7 int k, n, m; 8 int match[505], vis[505], g[505][505]; 9 10 inline int dfs(int u){11     for(int i = 1; i <= m; i++){12         if(g[u][i] && !vis[i]){13             vis[i] = 1;14             if(!match[i] || dfs(match[i])){15                 match[i] = u;16                 return 1;17             }18         }19     }20     return 0;21 }22 23 inline int hungary(){24     memset(match, 0, sizeof(match));25     int ans = 0;26     for(int i = 1; i <= n; i++){27         memset(vis, 0, sizeof(vis));28         if(dfs(i)) ans++;29     }30     return ans;31 }32 33 int main(){34     while(~scanf("%d%d%d", &k, &n, &m) && k != 0){35         memset(g, 0, sizeof(g)); 36         for(int i = 1; i <= k; i++){37             int a, b;38             scanf("%d%d", &a, &b);39             g[a][b] = 1;40         }41         printf("%d\n", hungary());42     }43     return 0;44 }