[18138] 리유나는 세일러복을 좋아해

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

18138번: 리유나는 세일러복을 좋아해

<문제>

집합의 원소의 개수 n, m과 n개의 집합 x, m개의 집합 y가 주어진다.

티셔츠와 카라를 합쳐서 세일러복을 만들 수 있다면 두 정점간 간선을 생성해준다. 

이후 이분매칭을 돌려주어 최대 매칭 수를 구하면 된다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
int n, m, ans, d[203];
bool check[203];
vector<int> adj[203];
bool f(int cur) {
    for (auto& next : adj[cur]) {
        if (check[next] == true) continue;
        check[next] = true;
        if (d[next] == 0 || f(d[next]) == true) {
            d[next] = cur;
            return true;
        }
    }
    return false;
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int i, j;
    cin >> n >> m;
    vector<int> x(n);
    vector<int> y(m);
    for (i = 0; i < n; i++) cin >> x[i];
    for (i = 0; i < m; i++) cin >> y[i];
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            double X = (double)x[i];
            double Y = (double)y[j];
            if (X * 0.5 <= Y && Y <= X * 0.75)
                adj[i + 1].push_back(j + 1);
            else if (x[i] <= y[j] && Y <= X * 1.25)
                adj[i + 1].push_back(j + 1);
        }
    }
    for (i = 1; i <= n; i++) {
        memset(check, 0, sizeof(check));
        if (f(i) == true) ans++;
    }
    cout << ans;
    return 0;
}