poj 1469 匈牙利算法求最大匹配
#include <stdio.h>#include <string.h>#define DEBUG#ifdef DEBUG#define debug(...) printf( __VA_ARGS__) #else#define debug(...)#endif#define N 301charweight[101][N];/* weight[x][y] = 1 表示学生x可以做课程y的助教 */charmat[N];/* mat[y] = x，表示定点y和x匹配 */charvisit[N];intnx, ny;int find(int x){inty;debug("go to X.%d\n", x);for (y = 1; y <= ny; y++) {if (!visit[y] && weight[x][y] > 0) {debug("go to Y.%d\n", y);visit[y] = 1;if (mat[y] == -1 || find(mat[y])) {debug("%d %d %d\n", x, y, mat[y]);/* 事实上程序实现的时候不用取反操作来标记哪些边已加入M，哪些边未加入M * 因为由mat数组和visit数组就可以确定，若mat[y] != -1， 则(mat[y],y)必然是一条加入M的边 * 只要visit[y] = 0，则(x,y)必然是一条没有加入M的边if (mat[y] != -1) {weight[mat[y]][y] *= -1;}weight[x][y] *= -1;*/mat[y] = x;return 1;}debug("return from Y.%d\n", y);}}return 0;}int main(){intt, m, x, y, possible;scanf("%d", &t);while (t--) {memset(weight, 0, sizeof(weight));memset(mat, -1, sizeof(mat));scanf("%d %d", &nx, &ny);/* X集合是课程，Y集合是学生， 课程应比学生少 */for (x = 1; x <= nx; x++) {scanf("%d", &m);while (m--) {scanf("%d", &y);weight[x][y] = 1;}}if (nx > ny) { printf("NO\n"); continue; }possible = 1;for (x = 1; x <= nx; x++) {memset(visit, 0, sizeof(visit));if (!find(x)) {/* X集合只要有一个定点找不到增广路径，则图必然不是完备匹配 */possible = 0;break;}debug("got an augmenting path...\n");}if (possible) {printf("YES\n");}else {printf("NO\n");}}return 0;}