给你学生数和课程数，以及学生上的课，需要满足两点，每个学生代表不同的课程，所有的课程都被代表。
即用学生数和课程数建图，求最大匹配数，如果匹配数等于课程数，即满足条件输出Yes，反之输出No
#include <queue> #include <stack> #include <math.h> #include <stdio.h> #include <stdlib.h> #include <iostream> #include <limits.h> #include <string.h> #include <algorithm> #define MAX 410 using namespace std; int p,n; int map[MAX][MAX]; int used[MAX],match[MAX]; bool Augment(int x) { int i; for(i=1; i<=p+n; i++) if( !used[i] && map[x][i] ) { used[i] = 1; if( match[i] == 0 || Augment(match[i]) ) //写错了 = =。。。查了半天。。 { match[i] = x; return true; } } return false; } int Hungary() { int i,sum = 0; memset(match,0,sizeof(match)); for(i=1; i<=p+n; i++) { memset(used,0,sizeof(used)); if( Augment(i) ) sum++; } return sum; } int main() { int ncases,num,to,i,ans; scanf("%d",&ncases); while( ncases-- ) { scanf("%d%d",&p,&n); memset(map,0,sizeof(map)); for(i=1; i<=p; i++) { scanf("%d",&num); while( num-- ) { scanf("%d",&to); map[i][to+p] = 1; } } ans = Hungary(); if( ans == p ) printf("YES/n"); else printf("NO/n"); } return 0; }
