Competitive-Programming/template/KM.cpp at master · HanaYukii/Competitive-Programming · GitHub

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
// Kuhn-Munkres (weighted bipartite matching)
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int MAXN = 1e6 + 5;
long long g[505][505];
long long lx[505], ly[505], slack[505];
int visx[505], visy[505], match[505];
int n;
long long sh = 1e11;
bool dfs(int now, bool upd) {
    if (visx[now]) {
        return 0;
    }
    visx[now] = 1;
    for (int i = 0 ; i < n ; i++) {
        if (visy[i]) continue;
        if (lx[now] + ly[i] == g[now][i]) {
            visy[i] = 1;
            if (match[i] == -1 || dfs(match[i], upd)) {
                if (upd)
                    match[i] = now;
                return 1;
            }
        }
        else {
            slack[i] = min(slack[i], lx[now] + ly[i] - g[now][i]);
        }
    }
    return 0;
}
bool augument() {
    for (int j = 0 ; j < n ; j++) {
        if (!visy[j] && slack[j] == 0) {
            visy[j] = 1;
            if (match[j] == -1 || dfs(match[j], 0)) {
                return 1;
            }
        }
    }
    return 0;
}
void relabel() {
    long long d = 1e15;
    for (int i = 0 ; i < n ; i++) {
        if (!visy[i]) {
            d = min(d, slack[i]);
        }
    }
    for (int i = 0 ; i < n ;i++) {
        if (visx[i]) {
            lx[i] -= d;
        }
    }
    for (int j = 0 ; j < n ;j++) {
        if (visy[j]) {
            ly[j] += d;
        }
        else {
            slack[j] -= d;
        }
    }
}
void go() {
    int m;
    cin >> n >> m;
    for (int i = 0 ; i < m ; i++) {
        int x, y, v;
        cin >> x >> y >> v;
        x--, y--;
        g[x][y] = v + sh;
    }
    long long ans = 0;
    for (int i = 0 ; i < n ; i++) {
        lx[i] = ly[i] = 0;
        for (int j = 0 ; j < n ; j++) {
            lx[i] = max(lx[i], g[i][j]);
        }
    }
    memset(match, -1, sizeof(match));
    for (int i = 0 ; i < n ; i++) {
        memset(slack, 0x3f, sizeof(slack));
        memset(visx, 0, sizeof(visx));
        memset(visy, 0, sizeof(visy));
        if (dfs(i, 1)) continue;
        while (!augument()) {
            relabel();
        }
        memset(visx, 0, sizeof(visx));
        memset(visy, 0, sizeof(visy));
        dfs(i, 1);
    }
    for (int i = 0 ; i < n ;i++) {
        ans += g[match[i]][i] - sh;
    }
    cout << ans << '\n';
    for (int i = 0 ; i < n ;i++) {
        cout << match[i] + 1 <<' ';
    }
    cout << '\n';
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int c = 0;
    int t;
    if (!c) {
        t = 1;
    }
    else {
        cin >> t;
    }
    while (t--) {
        go();
    }

}