POJ 2239 Selecting Courses(二分匹配)

题目链接：http://poj.org/problem?id=2239

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

Source

题意：

一个人在大学里选课，大学有很多门课，并且同一门课可以在一周的不同天不同时间出现多次。问他最多可以选多少门课（上课时间不能有冲突）；

思路：

建图：只需要把上课的时间累加处理一下，这样不同天的同一时间的课就能有所区分了，然后在求最大匹配数就好了！

代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define MAXN 517
int N;
int LN, RN;
int g[MAXN][MAXN];
int linker[MAXN];
bool used[MAXN];
int dfs(int L)//从左边开始找增广路径
{
    for(int R = 1 ; R <= RN ; R++ )
    {
        if(g[L][R] && !used[R])
        {
            //找增广路，反向
            used[R]=true;
            if(linker[R] == -1 || dfs(linker[R]))
            {
                linker[R]=L;
                return 1;
            }
        }
    }
    return 0;
}
int hungary()
{
    int res = 0 ;
    memset(linker,-1,sizeof(linker));
    for(int L = 1; L <= LN; L++)
    {
        memset(used,0,sizeof(used));
        if(dfs(L))
            res++;
    }
    return res;
}

int main()
{
    int n, m;
    int x, y;
    while(~scanf("%d",&n))
    {
        memset(g,0,sizeof(g));
        int maxx = 0;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&m);
            for(int j = 1; j <= m; j++)
            {
                scanf("%d%d",&x,&y);
                int tt = 12*x+y;
                g[i][tt] = 1;
                if(tt > maxx)
                    maxx = tt;
            }
        }
        LN = n;
        RN = maxx;
        int ans = hungary();
        printf("%d\n",ans);
    }
    return 0;
}

POJ 2239 Selecting Courses(二分匹配)

原文：http://blog.csdn.net/u012860063/article/details/39185063