主题链接：

题目大意：

学校总共同拥有N门课程，而且学校规定每天上12节可，一周上7天。

给你每门课每周上的次数，和哪一天哪一节

课上的。假设有多门课程在同一天同一节课上。那么你仅仅能选择当中一门。那么问题来了：最多能同一时候选多少

门课而不发生冲突呢。

输入说明：

先给你一个N。表示有N门课。接下来N行，每行第一个数字x，表示这门课每周上几节。接下来是x对数。第

一个数D表示是这一周哪一天上的，第二个数C表示是这一天哪一节课上的。

思路：

将这道题来看做二分图匹配问题。

建立一个二分图，一边代表课程，一边代表某一节课(将一周7*12节课按编

号1~7*12来排列)。将课程和该课程上的某一节课相应建边，再求这个二分图的最大匹配数就可以。这里用匈牙

利DFS版来做。

AC代码：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int MAXN = 330;int Map[MAXN][MAXN];int Mask[MAXN];int N,M;int cx[MAXN],cy[MAXN];int FindPath(int u){    for(int i = 1; i <= M; ++i)    {        if(Map[u][i] && !Mask[i])        {            Mask[i] = 1;            if(cy[i] == -1 || FindPath(cy[i]))            {                cy[i] = u;                cx[u] = i;                return 1;            }        }    }    return 0;}int MaxMatch(){    int res = 0;    for(int i = 1; i <= N; ++i)        cx[i] = -1;    for(int i = 1; i <= M; ++i)        cy[i] = -1;    for(int i = 1; i <= N; ++i)    {        if(cx[i] == -1)        {            for(int j = 1; j <= M; ++j)                Mask[j] = 0;            res += FindPath(i);        }    }    return res;}int main(){    int a,b,id;    while(~scanf("%d",&N))    {        memset(Map,false,sizeof(Map));        M = 7*12;        for(int i = 1; i <= N; ++i)        {            scanf("%d",&id);            for(int j = 1; j <= id; ++j)            {                scanf("%d%d",&a,&b);                Map[i][(a-1)*12+b] = 1;            }        }        printf("%d\n",MaxMatch());    }    return 0;}
        
       
      
     

版权声明：本文博主原创文章，博客，未经同意不得转载。