本文主要是介绍POJ2239_Selecting Courses(二分图最大匹配),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
解题报告
http://blog.csdn.net/juncoder/article/details/38154699
题目传送门
题意:
每天有12节课,一周上7天,一门课在一周有多天上课。求一周最多上几节课。
思路:
把课程看成一个集合,上课的时间看成一个集合,二分图就出来了。
#include <cstdio>
#include <cstring>
#include <iostream>using namespace std;
int n,day[10][15],mmap[500][500],vis[500],cnt,pre[500];
int dfs(int x)
{for(int i=n+1;i<cnt;i++){if(!vis[i]&&mmap[x][i]){vis[i]=1;if(pre[i]==-1||dfs(pre[i])){pre[i]=x;return 1;}}}return 0;
}
int main()
{int i,j,a,b,t;while(cin>>n){cnt=n+1;memset(mmap,0,sizeof(mmap));memset(day,0,sizeof(day));memset(pre,-1,sizeof(pre));for(i=1;i<=n;i++){cin>>t;for(j=1;j<=t;j++){cin>>a>>b;if(!day[a][b]){day[a][b]=cnt++;}mmap[i][day[a][b]]=1;}}int ans=0;for(i=1;i<=n;i++){memset(vis,0,sizeof(vis));ans+=dfs(i);}cout<<ans<<endl;}return 0;
}
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 8466 | Accepted: 3769 |
Description
There are 12 classes every day, and 7 days every week. There are hundreds of courses in the college, and teaching a course needs one class each week. To give students more convenience, though teaching a course needs only one class, a course will be taught several times in a week. For example, a course may be taught both at the 7-th class on Tuesday and 12-th class on Wednesday, you should assume that there is no difference between the two classes, and that students can select any class to go. At the different weeks, a student can even go to different class as his wish. Because there are so many courses in the college, selecting courses is not an easy job for Li Ming. As his good friends, can you help him?
Input
Output
Sample Input
5 1 1 1 2 1 1 2 2 1 2 2 2 3 2 3 3 1 3 3
Sample Output
4
这篇关于POJ2239_Selecting Courses(二分图最大匹配)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!