[C++] 상어의 저녁식사 (백준 1671번)

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

 

왼쪽 그룹을 먹는 상어, 오른쪽 그룹을 먹히는 상어라고 생각해보자.

일단 한 상어가 최대 두 개의 상어만 먹을 수 있다고 했으니, 왼쪽 그룹에는 상어 하나 당 두 개의 노드를 두고 (총 2 * n개) 오른쪽 그룹에는 상어 하나 당 하나의 노드를 둔 다음 (총 n개), 먹을 수 있는 관계인 경우에 연결해주면 될 것 같다.

 

참고로, "이미 잡아먹힌 상어는 다른 상어들을 잡아먹을 수 없다"는 조건은 크게 신경 쓸 필요가 없다. 매칭 결과를 보고 먹히는 쪽부터 실행한다고 생각할 수 있다.

 

이제 여기서 한 가지만 더 주의하면 된다. (처음에 이걸 고려를 못 했는데 예제가 친절해서 금방 알아차릴 수 있었다.)

두 상어가 크기, 속도, 지능이 전부 동일하면 서로 잡아먹을 수 있기 때문이다.

나는 이를 처리하기 위해서 전부 동일한 쌍의 경우에는, 번호가 작은 상어가 잡아먹을 수 있다고 임의로 정해두고 간선을 연결하였다.

 

// Reference: green55 teamnote
// https://github.com/green5555/Teamnote/blob/master/TeamNote/BiMatch.cpp

#include <bits/stdc++.h>
using namespace std;

const int MAX = 151;
struct BiMatching {
    vector<int> adj[MAX+5];
    int iter, A[MAX+5], B[MAX+5], was[MAX+5];

    bool dfs(int u) {
        was[u] = iter;
        for (int v : adj[u]) {
            if (B[v] == -1) {
                A[u] = v;
                B[v] = u;
                return true;
            }
        }
        for (int v : adj[u]) {
            if (was[B[v]] != iter && dfs(B[v])) {
                A[u] = v;
                B[v] = u;
                return true;
            }
        }
        return false;
    }

    int biMatch(int n=MAX) {
        fill(A, A+n, -1);
        fill(B, B+n, -1);
        fill(was, was+n, 0);
        iter = 0;
        int res = 0;
        while (true) {
            iter++;
            int add = 0;
            for (int i = 0; i < n; i++) {
                if (A[i] == -1 && dfs(i)) {
                    add++;
                }
            }
            if (add == 0) {
                break;
            }
            res += add;
        }
        return res;
    }
};

void solve() {
    BiMatching bm;

    int n;
    cin >> n;

    vector<int> a(n);
    vector<int> b(n);
    vector<int> c(n);
    for (int i = 0; i < n; i++) cin >> a[i] >> b[i] >> c[i];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            if (a[i] == a[j] && b[i] == b[j] && c[i] == c[j]) {
                if (i < j) {
                    bm.adj[i].push_back(j + 100);
                    bm.adj[i + 50].push_back(j + 100);
                }
            } else if (a[i] >= a[j] && b[i] >= b[j] && c[i] >= c[j]) {
                bm.adj[i].push_back(j + 100);
                bm.adj[i + 50].push_back(j + 100);
            }
        }
    }

    cout << n - bm.biMatch() << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T = 1;
    for (int i = 0; i < T; i++) {
        solve();
    }
}

(AC)