백준[1671] 상어의 저녁식사

문제 설명

문제 링크

http://icpc.me/1671

1671번: 상어의 저녁식사

풀이

이분 매칭을 이용하여 풀 수 있다.

먹을 수 있는 상어들을 이분 매칭으로 최대 매칭을 구하면 되는데 문제는 같은 상어끼리 먹고 먹히는 경우다.

모든 수치가 같다면, 서로 먹히고 먹을 수 있는데 이 경우를 예외 처리해줘야 한다. 수치가 같은 상어들이 있다면 이미 서로 먹지 못하게 자기보다 인덱스가 작은 상어는 먹지 못하도록 한다.

코드

#include <cstdio>
#include <cstring>

struct shark { int a, b, c; };
const int N = 55;
shark arr[N];
int B[N];
bool visited[N];
int n;

bool operator==(const shark &a, const shark &b) {
    if (a.a == b.a && a.b == b.b && a.c == b.c) return true;
    return false;
}

bool operator>(const shark &a, const shark &b) {
    if (a.a < b.a || a.b < b.b || a.c < b.c) return true;
    return false;
}

bool dfs(int a) {
    visited[a] = true;
    for (int i = 0; i < n; i++) {
        if (arr[a] == arr[i] && a < i) continue;
        if (i == a || arr[a] > arr[i]) continue;
        if (B[i] == -1 || !visited[B[i]] && dfs(B[i])) {
            B[i] = a;
            return true;
        }
    }
    return false;
}

int main() {
     scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int a, b, c; scanf("%d %d %d", &a, &b, &c);
        arr[i] = {a, b, c};
    }
    memset(B, -1, sizeof B);
    int ret = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2; j++) {
            memset(visited, false, sizeof visited);
            if (dfs(i)) ret++;
        }
    }
    printf("%d", n - ret);
}