[9576번] 책 나눠주기

문제 출처 :

https://www.acmicpc.net/problem/9576

알고리즘 분석 :

문제 해결에 필요한 사항

1. 이분 매칭 :: http://www.crocus.co.kr/499

전형적인 이분 매칭 문제이다.

학생 <-> 책으로 그룹을 나누고 이분 매칭을 해주면 된다.

한가지 그냥 조심해야 될 부분은, 입력 부분에서 a,b를 입력받으면 a~b를 전부 학생과 매칭 시켜주어야 한다는 것이다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <vector>
#include <memory.h>
 
#define MAX_N 1002
 
using namespace std;
 
int n, m;
int adj[MAX_N][MAX_N];
int aMatch[MAX_N];
int bMatch[MAX_N];
 
int visit[MAX_N];
int visitCnt = 1;
 
bool dfs(int a)
{
    if (visit[a] == visitCnt)
        return false;
 
    visit[a] = visitCnt;
    for (int i = 1; i <= n; i++)
    {
        if (adj[a][i])
        {
            int b = adj[a][i];
 
            if (bMatch[b] == -1 || dfs(bMatch[b]))
            {
                aMatch[a] = b;
                bMatch[b] = a;
 
                 return true;
            }
        }
    }
    return false;
}
int bipartiteMatch()
{
    memset(aMatch, -1, sizeof(aMatch));
    memset(bMatch, -1, sizeof(bMatch));
 
    int size = 0;
 
    for (int i = 1; i <= m; i++)
    {
        visitCnt++;
        size += dfs(i);
    }
 
    return size;
}
 
int main()
{
    int tCase;
 
    scanf("%d", &tCase);
    while (tCase--)
    {
        memset(adj, 0, sizeof(adj));
 
        scanf("%d %d", &n, &m);
 
        for (int i = 1; i <= m; i++)
        {
            int a, b;
            scanf("%d %d", &a, &b);
 
            for (int j = a; j <= b; j++)
                adj[i][j] = j;
        }
 
        int cnt = bipartiteMatch();
 
        printf("%d\n", cnt);
 
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>