POJ 2239-Selecting Courses(二分图_最大匹配+哈希建图)

Description

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

题意：有n门课程可以选择，接下来n行(编号为从1-n)，每行第一个数k，代表该门课程上课的时间点，接下来2*k个，每两个为一组(p，q)代表该节课在星期q的p班开始(一个12个班，一周7天)。求最多可以上几门课。

思路：如果不加上他的构图方式，就是一个纯的二分图求最大匹配。建图方式采用哈希表的方式，用p*12+q的方式存取，顺便还可以处理冲突。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int map[510][510];
int vis[510];
int link[510];
int n;
int dfs(int u)
{
    int i;
    for(i=1;i<=510;i++){
        if(map[u][i]&&!vis[i]){
            vis[i]=1;
            if(link[i]==-1||dfs(link[i])){
                link[i]=u;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    int i,j,k;
    int p,q;
    int sum;
    while(~scanf("%d",&n)){
    memset(link,-1,sizeof(link));
    memset(map,0,sizeof(map));
    for(i=1;i<=n;i++){
        scanf("%d",&k);
        while(k--){
            scanf("%d %d",&p,&q);
            //map[p*12+q][i]=1;
            map[i][p*12+q]=1;
        }
    }
    sum=0;
    for(i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i))
            {
                //printf("%d---->",dfs(i));
                sum++;
            }
    }
    printf("%d\n",sum);
    }
    return 0;
}

POJ 2239-Selecting Courses(二分图_最大匹配+哈希建图)

原文：http://blog.csdn.net/u013486414/article/details/42709685