백준 4966 - Cards (C++)

문제

• 문제 링크

  
   BOJ 4966 - Cards 
  

• 문제 요약

$N$개의 카드 집합과 $M$개의 카드 집합이 주어진다.
주어진 규칙에 따라 카드 쌍을 제거하려 할 때, 카드 쌍이 가장 많이 제거되는 경우를 찾아보자.

• 제한

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




$1 ≤ N, M ≤ 500$

$2 ≤ N_i, M_i ≤ 10^7$

알고리즘 분류

• 수학(math)
• 정수론(number_theory)
• 유클리드 호제법(euclidean)
• 이분 매칭(bipartite_matching)

풀이

$gcd(x, y) > 1$ 인 카드끼리 사이 좋게 제거할 수 있을 때, 가장 많이 제거 되도록 하는 경우를 찾으라고 한다.
파란색 카드 집합과 빨간색 카드 집합, 서로를 향해 간선을 세팅할 수 있고 $1 ≤ N, M ≤ 500$ 이므로..
이분 매칭 문제로 생각해 볼 수 있다.

각 카드 집합 간 모든 쌍에 대해 $gcd$를 검사 하고 그에 맞게 간선을 만들어주자.
이제 이분 매칭을 이용하면 최대 매칭 수를 $O(EV)$ 만에 찾아줄 수 있다.

$C$++이라 큰 걱정은 없다만.. 입력 포맷을 유의하자.

전체 코드

#include<bits/stdc++.h>
#define N 501
using namespace std;
 
vector <int> Gr[N];
int a[N], D[N], V[N];
 
int f(int p)
{
    for (auto& a : Gr[p])
        if (!V[a])
            if (V[a] = 1; !D[a] || f(D[a]))
                return D[a] = p, 1;
    return 0;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    for (int n, m, r{}; cin >> n >> m, n && m; r = 0)
    {
        for (int i(1); i <= n; cin >> a[i++]);
        for (int i(1); i <= m; i++)
        {
            int k; cin >> k;
            for (int j(1); j <= n; j++)
                if (gcd(a[j], k) > 1)
                    Gr[j].emplace_back(i);
        }
        for (int i(1); i <= n; r += f(i++))
            memset(V, 0, sizeof V);
        cout << r << '\n';
        for (int i(1); i < N; i++)
            Gr[i].clear(), D[i] = 0;
    }
}

comment

끝