程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 2239 哈希取址+二分匹配

POJ 2239 哈希取址+二分匹配

編輯：C++入門知識

B - Selecting Courses Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Submit Status

Description

It is well known that it is not easy to select courses in the college, for there is usually conflict among the time of the courses. Li Ming is a student who loves study every much, and at the beginning of each term, he always wants to select courses as more as possible. Of course there should be no conflict among the courses he selects.

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

The input contains several cases. For each case, the first line contains an integer n (1 <= n <= 300), the number of courses in Li Ming's college. The following n lines represent n different courses. In each line, the first number is an integer t (1 <= t <= 7*12), the different time when students can go to study the course. Then come t pairs of integers p (1 <= p <= 7) and q (1 <= q <= 12), which mean that the course will be taught at the q-th class on the p-th day of a week.

Output

For each test case, output one integer, which is the maximum number of courses Li Ming can select.

Sample Input

Sample Output

這題剛開始理解題目錯了，尼瑪，看到樣例中1 1有幾個，所以還以為是重復的呢，就只取了一個，然後就剩下（1，1），（2，2），（3，2），（3，3），然後就得出樣例答案為4.。直接WA一發，然後又重新讀題才發現理解錯題意了，暈……

題意原來是當前課程會在那些時間上幾次課，剛開始因為當前是一個結點了，然後周數與節數又有兩個數據，所以想想這兩個如果要想放在圖論中，那麼當然得把這兩個數據合成一個地址……哈哈這麼想著就有思路了……因為以前做過哈希方面的題，所以保存了好多哈希取址的計算函數，在實際中用得最多最高效也是最容易的就是BKDRHash哈希函數了，其計算式為：a*131+b這個就作為一個新地址存下來，也就是另一個結點……因為這個計算式已經被好多人證實過了，對於全部的（a,b），其取唯一地址的函數可以用這個計算，這個函數在實際中也是證明被用得最多的了，當然這個沒有處理地址沖突，所以地址還是有bug的，但是就這水題這個式子夠了……

然後有了這兩個結點當然就可以做邊了，匹配就是二分匹配了……

哈希不懂的可以看我的另一篇博文：http://blog.csdn.net/u011466175/article/details/17484687

#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 sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define MM 1000005
#define MN 100010
#define INF 55566677
#define eps 1e-7
using namespace std;
typedef long long ll;
vectorv[MN];
int vis[MN],pre[MN];
int dfs(int u)
{
    for(int i=0; i