BOJ)13166 범죄 파티

문제: icpc.me/13166

범죄자 N명과 친구 2*N명의 친구 관계와 임계점이 주어질 때 모든 범죄자가 친구랑 매칭 될 수 있는 파티 비용의 최솟값을 구하는 문제이다.

파티 비용의 최솟값을 파라메트릭 서치로 탐색할건데 이 때 탐색 기준은 mid를 파티 비용으로 정했을 때 모든 범죄자가 친구들과 매칭 되야 하므로 범죄자와 친구의 이분 매칭이 N이 됨을 기준으로 한다.

단, 정점의 개수가 20만이나 되므로 일반 이분매칭 소스로는 TLE를 보게되니 호프크로프트 카프 알고리즘을 이용하여 구해줘야 한다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 987654321
using namespace std;
struct hopcroft_karp {
    int n;
    vector<int> a, b, dist, match, work;
    vector<vector<int>> vt;
    hopcroft_karp(int n) :n(n) {
        a.assign(n + 1, -1);
        b.assign(n + 1, -1);
        dist.assign(n + 1, 0);
        match.assign(n + 1, 0);
        vt.resize(n + 1);
    }
    void addEdge(int x, int y) {
        vt[x].push_back(y);
    }
    void bfs() {
        queue<int> qu;
        for (int i = 1; i <= n; i++) {
            if (!match[i]) {
                dist[i] = 0;
                qu.push(i);
            }
            else
                dist[i] = INF;
        }
        while (qu.size()) {
            int here = qu.front();
            qu.pop();
            for (auto there : vt[here]) {
                if (b[there] != -1 && dist[b[there]] == INF) {
                    dist[b[there]] = dist[here] + 1;
                    qu.push(b[there]);
                }
            }
        }
    }
    bool dfs(int here) {
        for (int &i = work[here]; i < vt[here].size(); i++) {
            int there = vt[here][i];
            if (b[there] == -1 || dist[b[there]] == dist[here] + 1 && dfs(b[there])) {
                match[here] = true;
                a[here] = there;
                b[there] = here;
                return true;
            }
        }
        return false;
    }
    int solve() {
        int ret = 0;
        while (1) {
            work.assign(n + 1, 0);
            bfs();
            int flow = 0;
            for (int i = 1; i <= n; i++)
                if (!match[i] && dfs(i))flow++;
            if (!flow)break;
            ret += flow;
        }
        return ret;
    }
};
int n, x, y, z, w;
vector<vector<pair<int, int>>> v;
int main() {
    scanf("%d", &n);
    v.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d%d", &x, &y, &z, &w);
        v[i].push_back({ x,y });
        v[i].push_back({ z,w });
    }
    int lo = 0;
    int hi = 2999999;
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        hopcroft_karp hk(2 * n);
        for (int i = 1; i <= n; i++) {
            for (auto x : v[i]) {
                if (mid >= x.second)
                    hk.addEdge(i, x.first);
            }
        }
        if (hk.solve() == n)
            hi = mid;
        else
            lo = mid + 1;
    }
    printf("%d\n", lo);
    return 0;
}