본문 바로가기

알고리즘 관련/BOJ

BOJ)13166 범죄 파티

문제: icpc.me/13166


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


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


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



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#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 + 10);
        match.assign(n + 10);
        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] != -&& dist[b[there]] == INF) {
                    dist[b[there]] = dist[here] + 1;
                    qu.push(b[there]);
                }
            }
        }
    }
    bool dfs(int here) {
        for (int &= work[here]; i < vt[here].size(); i++) {
            int there = vt[here][i];
            if (b[there] == -|| dist[b[there]] == dist[here] + && 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 + 10);
            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<intint>>> 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(* 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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)2075 N번째 큰 수  (0) 2017.03.27
BOJ)1326 폴짝폴짝  (0) 2017.03.26
BOJ)3736 System Engineer  (0) 2017.03.25
BOJ)2660 회장뽑기  (0) 2017.03.23
BOJ)1755 숫자놀이  (0) 2017.03.23