백준 30976 - 사랑의 큐피드 (C++)

문제

• 문제 링크

  
   BOJ 30976 - 사랑의 큐피드 
  

• 문제 요약

$N$명의 여학생과 $M$명의 남학생에 대한 키 정보가 주어진다.
각 학생에 대한 선호 기준이 주어질 때, 성립될 수 있는 커플의 최대 수를 구해보자.

• 제한

TL : $1$ sec, ML : $512$ MB




$1 ≤ N, M ≤ 400$

$1 ≤ G_i, B_i, L_i, U_i ≤ 300$

한 학생이 둘 이상의 커플에 속할 수 없다.

알고리즘 분류

• 이분 매칭 (bipartite_matching)

풀이

여학생 집합과 남학생 집합은 서로 독립적이며, 간선은 서로 다른 집합에 대해서만 향할 수 있다.
즉, 문제의 조건대로 두 집합을 그래프로 모델링할 시 이 그래프는 반드시 이분 그래프의 형태를 띈다.

또한, $N, M ≤ 400$ 이고 최대 매칭 수를 찾아야 한다. 각 매칭은 일대응 대응이므로 이분 매칭을 이용해 약 $O(VE)$에 찾을 수 있다.

$1 ≤ i ≤ N$인 $i$와 $1 ≤ j ≤ M$인 $j$로 이루어지는 모든 $(i, j)$ 쌍에 대해 매칭 가능성을 검사해보자. 만약 $i$와 $j$가 매칭될 가능성이 있다면, $i$$→$$(400+j)$로 간선을 이어주자.

$400$을 더해주는 이유는 두 집합을 서로 다른 숫자집합에 두기 위함이다.

최종적으로 만들어진 이분 그래프에서 이분 매칭을 돌려주면 문제의 정답을 구할 수 있다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
vector <int> visit(808), assign(808);
vector <int> Gr[808];
 
int Match(int now)
{
    for (int& nxt : Gr[now])
        if (!visit[nxt])
        {
            visit[nxt] = 1;
            if (!assign[nxt] || Match(assign[nxt]))
                return assign[nxt] = now;
        }
    return 0;
}
int main()
{
    int n, m; cin >> n >> m;
 
    int a[4][404]{};
    for (int i{}; i < 4; i++)
        for (int j(1); j <= (i & 1 ? m : n); j++)
            scanf("%d", &a[i][j]);
 
    for (int i(1); i <= n; i++)
        for (int j(1); j <= m; j++)
            if (a[2][i] > a[1][j] && a[3][j] < a[0][i])
                Gr[i].push_back(400 + j);
 
    int ans{};
    for (int i(1); i <= n; i++)
    {
        visit = vector <int>(808);
        if (Match(i)) ans++;
    }
 
    cout << ans;
}

comment

끝