HDU 2063 过山车（二分图最大匹配问题）
/*基础的二分图最大匹配问题*/#include <iostream>using namespace std;const int nMax = 505;int map[nMax][nMax];//存储男女匹配模式int link[nMax];//与第i个女生相匹配的男生int useif[nMax];//是否被访问int K, M, N;bool can(int t){for(int i = 1; i <= N; ++ i){if(!useif[i] && map[t][i]){useif[i] = 1;if(link[i] == -1 || can(link[i]))//检查link[i]是否存在另外的匹配{link[i] = t;return 1;}}}return 0;}int main(){//freopen("f://data.in", "r", stdin);while(1){scanf("%d", &K);if(K == 0) break;scanf("%d%d", &M, &N);memset(map, 0, sizeof(map));memset(link, -1, sizeof(link));for(int i = 0; i < K; ++ i){int u, v;scanf("%d%d", &u, &v);map[u][v] = 1;}int num = 0;for(int i = 1; i <= M; ++ i){memset(useif, 0, sizeof(useif));if(can(i)) ++ num;//对M个女生进行查找增广轨}printf("%d\n", num);}return 0;}