POJ 2239 Selecting Courses【二分図最大マッチング】
1941 ワード
タイトルリンク:
http://poj.org/problem?id=2239
テーマ:
学校には全部でN科目があり、学校では毎日12時間、週に7日間通うことになっています.毎週の授業の回数と、いつの日かを教えてあげます.
授業中です.同じ日に同じ授業が複数ある場合は、そのうちの1つしか選択できません.では、質問です.せいぜい同時にどれだけ選ぶことができますか.
ドアの授業で衝突はありませんね.
説明を入力:
まずNをあげて、N科目があることを示します.次にN行、各行の最初の数字xは、この授業が毎週何回かあることを示します.次はx対数です.第
1つの数Dは今週のどの日を表し、2つ目の数Cはこの日のどの授業を表しています.
考え方:
この問題を二分図マッチング問題に見てみましょう.2分図を作成し、カリキュラムを代表しながら、ある授業を代表します(週7*12時間の授業を編集します.
号1~7*12で並びます).カリキュラムとそのカリキュラムのある授業をエッジにして、この二分図の最大マッチング数を求めればいいです.ここは匈牙で
利DFS版で作ります.
ACコード:
http://poj.org/problem?id=2239
テーマ:
学校には全部でN科目があり、学校では毎日12時間、週に7日間通うことになっています.毎週の授業の回数と、いつの日かを教えてあげます.
授業中です.同じ日に同じ授業が複数ある場合は、そのうちの1つしか選択できません.では、質問です.せいぜい同時にどれだけ選ぶことができますか.
ドアの授業で衝突はありませんね.
説明を入力:
まずNをあげて、N科目があることを示します.次にN行、各行の最初の数字xは、この授業が毎週何回かあることを示します.次はx対数です.第
1つの数Dは今週のどの日を表し、2つ目の数Cはこの日のどの授業を表しています.
考え方:
この問題を二分図マッチング問題に見てみましょう.2分図を作成し、カリキュラムを代表しながら、ある授業を代表します(週7*12時間の授業を編集します.
号1~7*12で並びます).カリキュラムとそのカリキュラムのある授業をエッジにして、この二分図の最大マッチング数を求めればいいです.ここは匈牙で
利DFS版で作ります.
ACコード:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 330;
int Map[MAXN][MAXN];
int Mask[MAXN];
int N,M;
int cx[MAXN],cy[MAXN];
int FindPath(int u)
{
for(int i = 1; i <= M; ++i)
{
if(Map[u][i] && !Mask[i])
{
Mask[i] = 1;
if(cy[i] == -1 || FindPath(cy[i]))
{
cy[i] = u;
cx[u] = i;
return 1;
}
}
}
return 0;
}
int MaxMatch()
{
int res = 0;
for(int i = 1; i <= N; ++i)
cx[i] = -1;
for(int i = 1; i <= M; ++i)
cy[i] = -1;
for(int i = 1; i <= N; ++i)
{
if(cx[i] == -1)
{
for(int j = 1; j <= M; ++j)
Mask[j] = 0;
res += FindPath(i);
}
}
return res;
}
int main()
{
int a,b,id;
while(~scanf("%d",&N))
{
memset(Map,false,sizeof(Map));
M = 7*12;
for(int i = 1; i <= N; ++i)
{
scanf("%d",&id);
for(int j = 1; j <= id; ++j)
{
scanf("%d%d",&a,&b);
Map[i][(a-1)*12+b] = 1;
}
}
printf("%d
",MaxMatch());
}
return 0;
}