CF 1728F - Fishermen 题解

1
#include <bits/stdc++.h>
2

3
#define N 1000010
4
#define M 1000010
5

6
using namespace std;
7
typedef long long ll;
8

9
struct Edge {
10
    int to, ne;
11
} edges[M << 1];
12
int h[N], idx = 0;
13
int a[N], b[N];
14
bool st[N];
15
int match[N];
16
vector<int> unq;
17
map<int, int> discrete;
18
int n;
19

20
void add(int a, int b) {
21
    idx++;
22
    edges[idx].to = b;
23
    edges[idx].ne = h[a];
24
    h[a] = idx;
25
}
26

27
bool hungary(int u) {
28
    for (int i = h[u]; ~i; i = edges[i].ne) {
29
        int j = edges[i].to;
30
        if (!st[j]) {
31
            st[j] = true;
32
            if (!match[j] || hungary(match[j])) {
33
                match[j] = u;
34
                return true;
35
            }
36
        }
37
    }
38
    return false;
39
}
40

41
int main() {
42
    ios::sync_with_stdio(false);
43
    cin.tie(nullptr);
44
    cout.tie(nullptr);
45

46
    memset(h, -1, sizeof h);
47

48
    cin >> n;
49
    for (int i = 1; i <= n; i++) cin >> a[i];
50
    for (int i = 1; i <= n; i++) {
51
        for (int k = 1; k <= n; k++) {
52
            unq.push_back(a[i] * k); // 处理倍数，预备去重
53
        }
54
    }
55
    sort(unq.begin(), unq.end());
56
    int cnt = unique(unq.begin(), unq.end()) - unq.begin(); // 去重，顺带升序排序
57
    int disc = 0;
58
    for (int i = 0; i < cnt; i++) {
59
        // 离散化
60
        discrete[unq[i]] = ++disc;
61
        b[disc] = unq[i]; // 去重前就已完成排序，直接赋值
62
    }
63
    for (int i = 1; i <= n; i++) {
64
        for (int k = 1; k <= n; k++) {
65
            add(discrete[a[i] * k] + n, i);
66
        }
67
    }
68
    ll ans = 0;
69
    int res = 0;
70
    for (int i = 1; i <= cnt; i++) {
71
        if (hungary(i + n)) {
72
            // 优化
73
            memset(st, false, sizeof st);
74
            res++;
75
            ans += b[i];
76
        }
77
        if (res == n) break; // 总共匹配n个a
78
    }
79
    cout << ans << endl;
80
    return 0;
81
}