POJ_2239_Selecting Courses

题意：一周上7天课，每天12节课，学校最多开设300节不同的课，每周每种课可以只有一个上课时间或者多个上课时间（上课内容一样），问一周最多可以选多少节课。

分析：二分图最大匹配，将一周84个时间点和可选的课程匹配，找出最大匹配，匈牙利。

总结：仿照poj2446的代码写的，熟悉了这种最简单的二分图匹配问题。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

#define Del(x,y) memset(x,y,sizeof(x))
int map[100][305],vis[305],link[305];
int n;

bool dfs(int x)
{
    for(int i=1;i<=n;i++)
        if(map[x][i]==1&&vis[i]==0)
        {
            vis[i]=1;
            if(link[i]==-1||dfs(link[i]))
            {
                link[i]=x;
                return true;
            }
        }
    return false;
}

void solve()
{
    int ans=0;
    Del(link,-1);
    for(int i=1;i<=84;i++)
    {
        Del(vis,0);
        if(dfs(i))
            ans++;
    }
    printf("%d
",ans);
}

int main()
{
    int t,p,q;
    while(~scanf("%d",&n))
    {
        Del(map,0);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&t);
            while(t--)
            {
                scanf("%d%d",&p,&q);
                map[12*(p-1)+q][i]=1;
            }
        }
        solve();
    }
    return 0;
}