题意：又是选课!N种课程，每种课程在不同时间可以选择，总共有7天*12节的时间可以选择课程，问最多可以选多少种课。
思路：建图。X区为12*7个结点，Y区为N种课，直接求二分最大匹配即可。
代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define PI acos(-1.0) #define mem(a,b) memset(a,b,sizeof(a)) #define maxn 500 #define maxm 60005 using namespace std; int head[maxn]; int t_c,t_s; struct Edge { int v,w; int next; } edge[maxm]; int top=0; int add_edge(int u,int v) { edge[top].v=v; edge[top].next=head[u]; head[u]=top++; return 0; } int from[maxn],tt; bool use[maxn]; bool match(int x) { for(int i=head[x]; i!=-1; i=edge[i].next) { int v=edge[i].v; if(!use[v]) { use[v]=1; if(from[v]==-1||match(from[v])) { from[v]=x; return true; } } } return false; } int hungary() { tt=0; mem(from,-1); for(int i=1; i<=t_c; i++) { mem(use,0); if(match(i)) tt++; } return tt; } int init() { mem(head,-1); top=0; return 0; } int main() { int ttt; while(scanf(%d,&t_c)!=EOF) { init(); for(int i=1; i<=t_c; i++) { scanf(%d,&ttt); for(int j=1; j<=ttt; j++) { int a,b; scanf(%d%d,&a,&b); add_edge(i,t_c+(a-1)*12+b); } } int res=hungary(); printf(%d ,res); } return 0; }