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[][],vis[],link[];

int n;

bool dfs(int x)

{

    for(int i=;i<=n;i++)

        if(map[x][i]==&&vis[i]==)

        {

            vis[i]=;

            if(link[i]==-||dfs(link[i]))

            {

                link[i]=x;

                return true;

            }

        }

    return false;

}

void solve()

{

    int ans=;

    Del(link,-);

    for(int i=;i<=;i++)

    {

        Del(vis,);

        if(dfs(i))

            ans++;

    }

    printf("%d\n",ans);

}

int main()

{

    int t,p,q;

    while(~scanf("%d",&n))

    {

        Del(map,);

        for(int i=;i<=n;i++)

        {

            scanf("%d",&t);

            while(t--)

            {

                scanf("%d%d",&p,&q);

                map[*(p-)+q][i]=;

            }

        }

        solve();

    }

    return ;

}

巴特西

POJ_2239_Selecting Courses

最新文章

热门文章