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;
}

1733번: 등번호

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

각 참가자마다 두 번호와 간선을 만들어 이분 그래프를 만든다.
이분 매칭을 해서 매칭 수가 n보다 작으면 불가능하고 n이면 각 참가자마다 매치된 번호를 출력한다.

Edmonds-Karp Algorithm을 사용하는 경우에는 visited 체크를 위해 배열을 초기화하는 대신에 탐색마다 다른 수를 덮어 씌어 TLE을 피해야 한다.

시간복잡도는 $O(n^2)$

#include<cstdio>
#include<vector>
using namespace std;
const int MX = 1e6;
int n, r, vis[MX + 1], rev[MX + 1], mc[MX + 1], cnt;
vector<int> adj[MX + 1];
int dfs(int h) {
    if (vis[h] == cnt) return 0;
    vis[h] = cnt;
    for (int it : adj[h]) if (!rev[it] || dfs(rev[it])) {
        mc[h] = it;
        rev[it] = h;
        return 1;
    }
    return 0;
}
int main() {
    scanf("%d", &n);
    for (int i = 1, x, y; i <= n; i++) scanf("%d%d", &x, &y), adj[i] = { x,y };
    for (int i = 1; i <= n; i++) ++cnt, r += dfs(i);
    if (r < n) puts("-1");
    else for (int i = 1; i <= n; i++) printf("%d\n", mc[i]);
    return 0;
}

매칭을 빠르게 구하기 위해 Hopcorft-Karp 알고리즘을 쓴다.
시간복잡도는 $O(n\sqrt n)$

#include<cstdio>
#include<vector>
using namespace std;
const int MX = 1e6;
int n, mc[MX + 1], lv[MX + 1], rev[MX + 1], q[MX], r;
vector<int> adj[MX + 1];
int bfs() {
    int flag = 0, h = 0, t = 0;
    for (int i = 1; i <= n; i++) {
        if (!mc[i]) q[t++] = i, lv[i] = 0;
        else lv[i] = -1;
    }
    for (; h < t; h++) for (int it : adj[q[h]]) {
        if (!rev[it]) flag = 1;
        else if (!~lv[rev[it]]) lv[rev[it]] = lv[q[h]] + 1, q[t++] = rev[it];
    }
    return flag;
}
int dfs(int h) {
    for (int it : adj[h]) if (!rev[it] || lv[h] < lv[rev[it]] && dfs(rev[it])) {
        mc[h] = it;
        rev[it] = h;
        return 1;
    }
    lv[h] = 0;
    return 0;
}
int main() {
    scanf("%d", &n);
    for (int i = 1, x, y; i <= n; i++) scanf("%d%d", &x, &y), adj[i] = { x,y };
    while (bfs()) for (int i = 1; i <= n; i++) if (!mc[i]) r += dfs(i);
    if (r < n) puts("-1");
    else for (int i = 1; i <= n; i++) printf("%d\n", mc[i]);
    return 0;
}

3736번: System Engineer

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

이분 매칭 문제이다. Hopcroft–Karp Algorithm 알고리즘을 써야 TLE를 피할 수 있다.

시간복잡도는 $O(n^{2.5})$

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
vector<int> adj[10000];
int n, ck[10000], rev[10000], lv[10000];
bool BFS() {
    queue<int> q;
    fill(lv, lv + n, -1);
    for (int i = 0; i < n; i++) if (!ck[i]) q.push(i), lv[i] = 0;
    int flag = 0;
    while (!q.empty()) {
        int h = q.front();
        q.pop();
        for (int it : adj[h]) {
            if (!~rev[it]) flag = 1;
            else if (!~lv[rev[it]]) lv[rev[it]] = lv[h] + 1, q.push(rev[it]);
        }
    }
    return flag;
}
int DFS(int h) {
    for (int it : adj[h]) if (!~rev[it] || lv[h] < lv[rev[it]] && DFS(rev[it])) {
        rev[it] = h;
        return 1;
    }
    lv[h] = 0;
    return 0;
}
int main() {
    while (~scanf("%d", &n)) {
        int r = 0;
        for (int i = 0, x, m, y; i < n; i++) {
            scanf("%d: (%d)", &x, &m);
            adj[x].clear();
            for (int j = 0; j < m; j++) scanf("%d", &y), adj[x].push_back(y - n);
        }
        fill(rev, rev + n, -1);
        fill(ck, ck + n, 0);
        while (BFS()) {
            for (int i = 0; i < n; i++) if (!lv[i] && DFS(i)) ck[i] = 1, r++;
        }
        printf("%d\n", r);
    }
    return 0;
}