大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
主题链接：
http://poj.org/problem?id=2239
题目大意：
学校总共同拥有N门课程，而且学校规定每天上12节可，一周上7天。
给你每门课每周上的次数，和哪一天哪一节
课上的。假设有多门课程在同一天同一节课上。那么你仅仅能选择当中一门。那么问题来了：最多能同一时候选多少
门课而不发生冲突呢。
输入说明：
先给你一个N。表示有N门课。接下来N行，每行第一个数字x，表示这门课每周上几节。接下来是x对数。第
一个数D表示是这一周哪一天上的，第二个数C表示是这一天哪一节课上的。
思路：
将这道题来看做二分图匹配问题。
建立一个二分图，一边代表课程，一边代表某一节课(将一周7*12节课按编
号1~7*12来排列)。将课程和该课程上的某一节课相应建边，再求这个二分图的最大匹配数就可以。这里用匈牙
利DFS版来做。
AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
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;
}
版权声明：本文博主原创文章，博客，未经同意不得转载。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116838.html原文链接：https://javaforall.net
