/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2011 panyanyany All rights reserved.
URL : http://poj.org/problem?id=2239
Name : 2239 Selecting Courses
Date : Monday, November 28, 2011
Time Stage : one hour
Result:
9607451 panyanyany
2239
Accepted 256K 32MS C++
1360B 2011-11-28 20:46:55
Test Data :
Review :
前言:
貌似是比较裸的二分图之最大匹配,也许是因为最近做的题相对多一点吧,所以比较容易
看出来。
思路:
把所有的课程(course)归类为一个点集,所有的课时(class)归类为另一个点集,
课程编号为:1,2,3,...,300 ;
课时编号为:1,2,3,...,84 (因为一星期共有 7*12 节课);
每个课程有n个课时,即课程与课时之间有n条连线(或边)
怎样才能上最多的课,即求课程与课时之间的最大匹配
//----------------------------------------------------------------------------*/
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std ;
#define MAXCOURSE 301
#define MAXCLASS 85
int n, t, p, q ;
int link[MAXCOURSE] ;
bool cover[MAXCLASS] ;
vector<int> graph[MAXCOURSE] ;
bool find (int cur)
{
int i, j ;
for (i = 0 ; i < graph[cur].size () ; ++i)
{
j = graph[cur][i] ;
if (cover[j] == false)
{
cover[j] = true ;
if (link[j] == 0 || find (link[j]))
{
link[j] = cur ;
return true ;
}
}
}
return false ;
}
int main ()
{
int i, j ;
int x, y ;
int sum ;
while (~scanf ("%d", &n))
{
for (i = 1 ; i <= n ; ++i)
{
graph[i].clear () ;
scanf ("%d", &t) ;
for (j = 1 ; j <= t ; ++j)
{
scanf ("%d%d", &x, &y) ;
graph[i].push_back ((x-1)*12 + y) ;
}
}
sum = 0 ;
memset (link, 0, sizeof (link)) ;
for (i = 1 ; i <= n ; ++i)
{
memset (cover, 0, sizeof (cover)) ;
sum += find (i) ;
}
printf ("%d\n", sum) ;
}
return 0 ;
}
分享到:
相关推荐
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
ACM POJ 解题报告北大POJ 大量解题代码
北大poj解题报告,希望能帮到软件工程的同学,每天一道,持之以恒,熟能生巧,与您共勉!
北大POJ初级题-数据结构:解题报告+AC代码
如果你为在poj上找不到解题思路而痛苦,那么这本书可以为你带来惊喜,里面包括了poj上一部分题解题报告~
北大POJ初级-所有题目AC代码+解题报告
POJ入门题库,有源代码,部分有解题思路,还有输出截图
初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) ... (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) ......
北大POJ经典结题报告 北大POJ经典结题报告 北大POJ经典结题报告 注重方法,内容详尽,物超所值
很多的POJ题目答案!1000~1008,1011~1014,1016,1017,1019,1028,1032,1045,1046,1047,1050,1061,1067,1068,1088,1102,1159,1163,1183,1207,1218,1226,1247,1256,1258,1298,1316,1323,...
北大POJ初级-图算法 解题报告+AC代码
此压缩包包含北京大学POJ题目的绝大部分解题代码,一道题目有不同语言的编程,但主要是C++语言,仅供大家学习之用。
poj1691解题报告 题目来源:http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1691(POJ No.1691) 解法: 搜索
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
POJ上面题目的解题报告。涵盖挺多的。可作参考。代码都正确。ACM新手入门必下~~ 加油...
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
北大POJ初级-简单搜索 解题报告+AC代码
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告