[백준]리유나는 세일러복을 좋아해(18138)

문제 링크 : [백준]리유나는 세일러복을 좋아해(18138)

문제 설명

N개의 흰티와 M개의 카라의 너비가 주어집니다.
흰티와 카라를 합쳐서 세일러복을 최대한 많이 만들려고 하는데, 합치기 위한 조건은 아래와 같습니다.

1. 흰티 너비/2 <= 카라 너비 <= 흰티 너비 * 3/4
2. 흰티 너비 <= 카라 너비 <= 흰티 너비 * 5/4
   둘 중 하나의 조건을 만족하면 세일러복을 만들 수 있습니다.
   위 조건들을 만족하면서 최대로 만들 수 있는 세일러복 갯수를 구하세요.

   입력

   N(수의 갯수, 1 <= N <= 50)
   K(더할 수, 1 <= K <= 10)
   V_i(주어진 수, 1 <= V_i <= N)

   5 5
   1
   3
   5
   7
   10
   2
   4
   8
   5
   6

출력

4

카테고리

#이분매칭

시간 복잡도 상한

O(N³) 혹은 O(M³)

해결 방법

1. 흰티를 하나의 그룹(그룹A), 카라를 하나의 그룹(그룹B)으로 만들고, 두 그룹이 중복되지 않게 최대한 많은 매핑관계를 만들 수 있는 이분 매칭을 사용하면 됩니다.
2. 두 그룹간 엣지 관계는 위에서 주어진 조건에 만족하는 경우에 엣지를 만들어 그래프를 완성시킵니다.
3. 완성된 그래프를 가지고 이분매칭 알고리즘을 사용하여 최대 갯수를 구합니다.

시간복잡도

O(N*N)

코드

#include<cstdio>
#include<vector>
#include<string.h>
using namespace std;
int n,m,v[201],f[201],i,j;
double d[201],e[201];
vector<int>w[201];
int r(int p){
    if(v[p])return 0;
    v[p]=1;
    for(int x:w[p]){
        if(!f[x]||r(f[x])){
            f[x]=p;
            return 1;
        }
    }
    return 0;
}
int main(){
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%lf",d+i);
    for(i=1;i<=m;i++)scanf("%lf",e+i);
    for(i=1;i<=n;i++)for(j=1;j<=m;j++)if((d[i]*0.5<=e[j]&&e[j]<=d[i]*0.75)||(d[i]<=e[j]&&e[j]<=d[i]*1.25))w[i].push_back(j);
    for(i=1,j=0;i<=n;i++)memset(v,0,sizeof(v)),j+=r(i);
    printf("%d",j);
}