题目链接：【http://hihocoder.com/problemset/problem/1393】
题意：中文题意。
题解：二分图的多重匹配。主要是建图然后跑一个最带流，再判断一下就可以了。
建图：首先要保证每个学生最多选择a[i]节课，那么我们建立一个超级起点S,S->学生，流量为学生最多选的课数，然后每个学生向它喜欢的课程建立一条流量为1的边，然后又要保证每个项目的人数，每个项目向超级汇点T建立一条流量为M[i]的边，表示每节课最多上M[i]个人。然后跑最大流，判断指向终点的边是不是满载就可以了。
【http://blog.csdn.net/tramp_1/article/details/52663763】推荐博客。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 1050; const int maxm = 10050; const int INF = 0x3f3f3f3f; struct Edge { int to, next, cap, flow; Edge(int to = 0, int next = 0, int cap = 0, int flow = 0): to(to), next(next), cap(cap), flow(flow) {} } edge[maxm]; int head[maxn], tot; void init() { memset(head, -1, sizeof(head)); tot = 0; } void addedge(int u, int v, int w, int rw = 0) { edge[tot] = Edge(v, head[u], w, 0); head[u] = tot++; edge[tot] = Edge(u, head[v], rw, 0); head[v] = tot++; } int gap[maxn], dep[maxn], pre[maxn], cur[maxn]; int sap(int st, int ed, int nodenum) { memset(gap, 0, sizeof(gap)); memset(dep, 0, sizeof(dep)); memcpy(cur, head, sizeof(head)); int u = st; pre[u] = -1; gap[0] = nodenum; int ans = 0; while(dep[st] < nodenum) { if(u == ed) { int Min = INF; for(int i = pre[u]; i != -1; i = pre[edge[i ^ 1].to]) if(Min > edge[i].cap - edge[i].flow) Min = edge[i].cap - edge[i].flow; for(int i = pre[u]; i != -1; i = pre[edge[i ^ 1].to]) { edge[i].flow += Min; edge[i ^ 1].flow -= Min; } u = st; ans += Min; continue; } bool fg = false; int v; for(int i = cur[u]; i != -1; i = edge[i].next) { v = edge[i].to; if(edge[i].cap - edge[i].flow && dep[v] + 1 == dep[u]) { fg = true; cur[u] = pre[v] = i; break; } } if(fg) { u = v; continue; } int Min = nodenum; for(int i = head[u]; i != -1; i = edge[i].next) if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min) { Min = dep[edge[i].to]; cur[u] = i; } gap[dep[u]]--; if(!gap[dep[u]]) return ans; dep[u] = Min + 1; gap[dep[u]]++; if(u != st) u = edge[pre[u] ^ 1].to; } return ans; } int T, n, m; int main () { scanf("%d", &T); while(T--) { init(); scanf("%d%d", &n, &m); int num = 0; for(int i = 1; i <= m; i++) { int t; scanf("%d", &t); num += t; addedge(n + i, n + m + 1, t); } for(int i = 1; i <= n; i++) { int x, t; scanf("%d%d", &t, &x); addedge(0, i, t); for(int j = 1; j <= x; j++) { scanf("%d", &t); addedge(i, n + t, 1); } } int flow = sap(0, n + m + 1, n + m + 2); if(flow == num) printf("Yes\n"); else printf("No\n"); } return 0; }