Courses HDU - 1083
题意：
有p个课程，n个学生。
问：
是否存在一种匹配，使得每个课程都要有学生。（且不能有多余的学生）。
思路：
二分最大匹配。从课程出发去匹配学生
反思：
- 初始化别乱用。（mst就mst，其他算了ε=ε=ε=(￣▽￣)）
mst(head,-1);mst(vis,0);// for(int i=0; i<=p*n; i++)head[i]=-1,vis[i]=0;之所以wa是因为1*1的情况。
- 对于题目求什么，那就从什么出发
二分最大匹配。从
课程出发去匹配学生
AC
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#define mst(x,a) memset(x,a,sizeof(x))
#define fzhead EDGE(int _to, int _next)
#define fzbody to(_to), next(_next)
using namespace std;
const int maxn=400+10;
const int maxm=3e4+10;
struct EDGE{int to,next;EDGE(){}fzhead:fzbody{}
}e[maxm];
int cnt,head[maxn],vis[maxn];
bool used[maxn];
void add(int bg, int to){e[cnt]=EDGE(to,head[bg]);head[bg]=cnt++;
}
bool dfs(int u){for(int i=head[u]; i!=-1; i=e[i].next){int v=e[i].to;if(!used[v]){used[v]=1;if(!vis[v]||dfs(vis[v])){vis[v]=u;return true;}}}return false;
}
int n,p;
int max_match(){int ans=0;for(int i=1; i<=p; i++){mst(used,0);//ans+=dfs(i);if(!dfs(i))return false;ans++;}//cout<<ans<<endl;return ans==p;
}
int main()
{int t;scanf("%d", &t);while(t--){cnt=0;scanf("%d%d",&p, &n);mst(head,-1);mst(vis,0);// for(int i=0; i<=p*n; i++)head[i]=-1,vis[i]=0;for(int i=1; i<=p; i++){int num;scanf("%d", &num);for(int j=1; j<=num; j++){int v;scanf("%d", &v);add(i,p+v);}}if(max_match())puts("YES");//printf("YES");else puts("NO");}return 0;
}