13166번: 범죄 파티

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


주어진 문제는 친구 및 용의자를 노드, 임계값이 x이하인 관계들을 간선으로 나타내어 그래프를 만들었을 때, 모든 용의자에 대해 매칭이 가능한지 판단하는 문제로 바꿀 수 있다.
각 노드의 최대 차수는 2이므로 가능한 각 연결 그래프의 모양은 일자 아니면 링형 밖에 없다. 이러한 모양의 연결 그래프에서는 노드 수가 짝수이면 모든 노드의 매칭이 가능하고 홀수이면 불가능하다.
임계값이 작은 관계부터 보며 간선을 추가한다. 모든 연결그래프의 노드 수가 짝수가 되었을 때, 직전에 추가한 간선에 관한 임계값이 답이 된다. 모든 간선을 추가하고도 모든 연결그래프의 노드 수가 짝수가 되지 않는다면 불가능하다.

시간복잡도는 $O(n\lg n)$

#include<cstdio>
#include<algorithm>
using namespace std;
int n, sz[600001], p[600001], r;
struct st {
    int x, y, c;
}l[400001];
int f(int x) { return x^p[x] ? p[x] = f(p[x]) : x; }
int main() {
    scanf("%d", &n);
    for (int i = 1, a, b, c, d; i <= n; i++) {
        scanf("%d%d%d%d", &a, &b, &c, &d);
        l[i] = { i,a + n,b };
        l[i + n] = { i,c + n,d };
    }
    for (int i = 1; i <= 6 * n; i++) sz[i] = 1, p[i] = i;
    sort(l + 1, l + 2 * n + 1, [](st i, st j) {return i.c < j.c; });
    r = n;
    for (int i = 1; i <= 2 * n; i++) {
        int ra = f(l[i].x), rb = f(l[i].y);
        r -= sz[ra] & sz[rb];
        if (!r) printf("%d", l[i].c), exit(0);
        sz[ra] ^= sz[rb];
        p[rb] = ra;
    }
    puts("-1");
    return 0;
}

비용을 기준으로 파라매트릭 서치를 해볼 수 있다.
임계값이 정한 비용 이하인 친구 - 용의자 관계를 가지고 이분 그래프를 만든 뒤, Hopcroft-Karp algorithm으로 이분 매칭을 해본다.

시간복잡도는 $O(n^{1.5}\lg L)$ // L: 임계값의 최댓값

#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
const int MXN = 2e5;
int n, lv[MXN + 1], rev[MXN * 2 + 1], mc[MXN + 1], mid;
vector<pair<int, int> > adj[MXN + 1];
bool bfs() {
    memset(lv, -1, sizeof(lv));
    queue<int> q;
    bool flag = false;
    for (int i = 1; i <= n; i++) if (!mc[i]) q.push(i);
    while (!q.empty()) {
        int h = q.front();
        q.pop();
        for (auto it : adj[h]) if (it.second <= mid) {
            if (!rev[it.first]) flag = true;
            else if (!~lv[rev[it.first]]) lv[rev[it.first]] = lv[h] + 1, q.push(rev[it.first]);
        }
    }
    return flag;
}
bool dfs(int h) {
    for (auto it : adj[h]) if (it.second <= mid && (!rev[it.first] || lv[h] < lv[rev[it.first]] && dfs(rev[it.first]))) {
        rev[it.first] = h;
        return true;
    }
    lv[h] = 0;
    return false;
}
bool f() {
    memset(rev, 0, sizeof(rev));
    memset(mc, 0, sizeof(mc));
    int r = 0;
    while (bfs()) for (int i = 1; i <= n; i++) if (!mc[i] && dfs(i)) mc[i] = 1, r++;
    return r == n;
}
int main() {
    scanf("%d", &n);
    for (int i = 1, a, b, c, d; i <= n; i++) scanf("%d%d%d%d", &a, &b, &c, &d), adj[i] = { { a,b },{ c,d } };
    int low = 0, up = 1e6;
    while (low <= up) {
        mid = (low + up) / 2;
        f() ? up = mid - 1 : low = mid + 1;
    }
    printf("%d", low > 1e6 ? -1 : low);
    return 0;
}