GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 138 / 0 / 138
Functions: 100.0% 18 / 0 / 18
Branches: 99.0% 194 / 0 / 196
src/graph/blossom/w/lib.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "../../../util/alias/others/lib.hpp"
4
5 namespace tifa_libs {
6
7 //! 1-indexed, [1, n]
8 template <class T>
9 struct blossomw {
10 struct TIFA {
11 u32 u, v;
12 T w;
13 };
14 vvec<TIFA> g;
15 u32 n, nx;
16 vec<T> lab;
17 vecu match, slack, st, par, s, aux;
18 vvecu flo_from, flo;
19 std::queue<u32> q;
20
21 24 explicit blossomw(u32 n) NE { init(n); }
22 24 void init(u32 n_) NE {
23 72 n = n_, g = vvec<TIFA>(n * 2 + 1, vec<TIFA>(n * 2 + 1));
24 192 lab = vec<T>(n * 2 + 1), match = vecu(n * 2 + 1), slack = vecu(n * 2 + 1), st = vecu(n * 2 + 1);
25 144 par = vecu(n * 2 + 1), s = vecu(n * 2 + 1), aux = vecu(n * 2 + 1);
26 96 flo_from = vvecu(n * 2 + 1, vecu(n + 1)), flo = vvecu(n * 2 + 1);
27
2/2
✓ Branch 0 taken 8163 times.
✓ Branch 1 taken 24 times.
 8187 flt_ (u32, u, 1, n + 1)
28
2/2
✓ Branch 2 taken 4010779 times.
✓ Branch 3 taken 8163 times.
 4018942 flt_ (u32, v, 1, n + 1) g[u][v] = {u, v, 0};
29 24 }
30
31 863250 CEXP void add_edge(u32 u, u32 v, T w) NE { g[u][v].w = g[v][u].w = w; }
32 24 vec<edge_t<T>> operator()(T inf = std::numeric_limits<T>::max()) NE {
33 24 nx = n, st[0] = 0;
34
2/2
✓ Branch 1 taken 16326 times.
✓ Branch 2 taken 24 times.
 16350 flt_ (u32, i, 1, 2 * n + 1) aux[i] = 0;
35
2/2
✓ Branch 4 taken 8163 times.
✓ Branch 5 taken 24 times.
 8187 flt_ (u32, i, 1, n + 1) match[i] = 0, st[i] = i, flo[i].clear();
36 24 T wmax = 0;
37
2/2
✓ Branch 0 taken 8163 times.
✓ Branch 1 taken 24 times.
 8187 flt_ (u32, u, 1, n + 1)
38
2/2
✓ Branch 0 taken 4010779 times.
✓ Branch 1 taken 8163 times.
 4018942 flt_ (u32, v, 1, n + 1)
39
2/2
✓ Branch 0 taken 8163 times.
✓ Branch 1 taken 4002616 times.
 4010779 flo_from[u][v] = (u == v ? u : 0), wmax = max(wmax, g[u][v].w);
40
2/2
✓ Branch 1 taken 8163 times.
✓ Branch 2 taken 24 times.
 8187 flt_ (u32, u, 1, n + 1) lab[u] = wmax;
41
2/2
✓ Branch 1 taken 3543 times.
✓ Branch 2 taken 24 times.
 3567 while (matching(inf));
42 24 vec<edge_t<T>> ans;
43
2/2
✓ Branch 0 taken 8163 times.
✓ Branch 1 taken 24 times.
 8187 flt_ (u32, u, 1, n + 1)
44
6/6
✓ Branch 1 taken 7086 times.
✓ Branch 2 taken 1077 times.
✓ Branch 4 taken 3543 times.
✓ Branch 5 taken 3543 times.
✓ Branch 6 taken 3543 times.
✓ Branch 7 taken 4620 times.
 8163 if (match[u] && match[u] < u) ans.emplace_back(g[u][match[u]].w, u, match[u]);
45 24 return ans;
46 }
47
48 private:
49 834051944 CEXP T e_delta(TIFA CR e) NE { return lab[e.u] + lab[e.v] - g[e.u][e.v].w * 2; }
50 263150283 CEXP void upd_slack(u32 u, u32 x) NE {
51
6/6
✓ Branch 1 taken 261416201 times.
✓ Branch 2 taken 1734082 times.
✓ Branch 10 taken 7113992 times.
✓ Branch 11 taken 254302209 times.
✓ Branch 12 taken 8848074 times.
✓ Branch 13 taken 254302209 times.
 263150283 if (!slack[x] || e_delta(g[u][x]) < e_delta(g[slack[x]][x])) slack[x] = u;
52 263150283 }
53 18714 CEXP void set_slack(u32 x) NE {
54 18714 slack[x] = 0;
55
2/2
✓ Branch 0 taken 9334358 times.
✓ Branch 1 taken 18714 times.
 9353072 flt_ (u32, u, 1, n + 1)
56
8/8
✓ Branch 2 taken 9222476 times.
✓ Branch 3 taken 111882 times.
✓ Branch 5 taken 8034881 times.
✓ Branch 6 taken 1187595 times.
✓ Branch 9 taken 1565841 times.
✓ Branch 10 taken 6469040 times.
✓ Branch 11 taken 1565841 times.
✓ Branch 12 taken 7768517 times.
 9334358 if (g[u][x].w > 0 && st[u] != x && s[st[u]] == 0) upd_slack(u, x);
57 18714 }
58 1094153 void q_push(u32 x) NE {
59
2/2
✓ Branch 0 taken 1093902 times.
✓ Branch 1 taken 251 times.
 1094153 if (x <= n) q.push(x);
60 else
61
2/2
✓ Branch 7 taken 1059 times.
✓ Branch 8 taken 251 times.
 1310 for (auto t : flo[x]) q_push(t);
62 1094153 }
63 2502044 CEXP void set_st(u32 x, u32 b) NE {
64
2/2
✓ Branch 1 taken 300919 times.
✓ Branch 2 taken 2201125 times.
 2502044 if (st[x] = b; x > n)
65
2/2
✓ Branch 7 taken 2470569 times.
✓ Branch 8 taken 300919 times.
 2771488 for (auto t : flo[x]) set_st(t, b);
66 2502044 }
67 7571 CEXP u32 get_pr(u32 b, u32 xr) NE {
68
2/2
✓ Branch 5 taken 146 times.
✓ Branch 6 taken 7425 times.
 7571 if (u32 pr = u32(find(flo[b], xr) - begin(flo[b])); pr & 1) {
69 146 reverse(begin(flo[b]) + 1, end(flo[b]));
70 146 return u32(flo[b].size() - pr);
71 7425 } else return pr;
72 }
73 43340 CEXP void set_match(u32 u, u32 v) NE {
74 43340 auto [eu, ev, _] = g[u][v];
75
2/2
✓ Branch 1 taken 39160 times.
✓ Branch 2 taken 4180 times.
 43340 if (match[u] = ev; u <= n) return;
76 4180 u32 xr = flo_from[u][eu], pr = get_pr(u, xr);
77
2/2
✓ Branch 5 taken 8732 times.
✓ Branch 6 taken 4180 times.
 12912 flt_ (u32, i, 0, pr) set_match(flo[u][i], flo[u][i ^ 1]);
78 4180 set_match(xr, v), rotate(flo[u], begin(flo[u]) + pr);
79 }
80 7086 CEXP void augment(u32 u, u32 v) NE {
81 11671 while (true) {
82 18757 u32 xnv = st[match[u]];
83
2/2
✓ Branch 1 taken 7086 times.
✓ Branch 2 taken 11671 times.
 18757 if (set_match(u, v); !xnv) return;
84 11671 set_match(xnv, st[par[xnv]]), u = st[par[xnv]], v = xnv;
85 }
86 }
87 7619 u32 lca(u32 u, u32 v) NE {
88 static u32 t = 0;
89
4/4
✓ Branch 1 taken 40896 times.
✓ Branch 2 taken 18637 times.
✓ Branch 3 taken 15094 times.
✓ Branch 4 taken 3543 times.
 59533 for (++t; u || v; swap(u, v)) {
90
2/2
✓ Branch 0 taken 15094 times.
✓ Branch 1 taken 40896 times.
 55990 if (!u) continue;
91
2/2
✓ Branch 1 taken 4076 times.
✓ Branch 2 taken 36820 times.
 40896 if (aux[u] == t) return u;
92
2/2
✓ Branch 3 taken 26794 times.
✓ Branch 4 taken 10026 times.
 36820 if (aux[u] = t; (u = st[match[u]])) u = st[par[u]];
93 }
94 3543 return 0;
95 }
96 4076 CEXP void add_blossom(u32 u, u32 anc, u32 v) NE {
97 4076 u32 b = n + 1;
98
6/6
✓ Branch 0 taken 178611 times.
✓ Branch 1 taken 714 times.
✓ Branch 3 taken 175249 times.
✓ Branch 4 taken 3362 times.
✓ Branch 5 taken 175249 times.
✓ Branch 6 taken 4076 times.
 179325 while (b <= nx && st[b]) ++b;
99
2/2
✓ Branch 0 taken 714 times.
✓ Branch 1 taken 3362 times.
 4076 if (b > nx) ++nx;
100 4076 lab[b] = s[b] = 0, match[b] = match[anc], flo[b] = {anc};
101 20380 auto blossom = [&](u32 x) NE {
102
2/2
✓ Branch 9 taken 13374 times.
✓ Branch 10 taken 8152 times.
 21526 for (u32 y; x != anc; x = st[par[y]]) flo[b].push_back(x), flo[b].push_back(y = st[match[x]]), q_push(y);
103 };
104 4076 blossom(u), reverse(begin(flo[b]) + 1, end(flo[b])), blossom(v), set_st(b, b);
105
2/2
✓ Branch 4 taken 2352387 times.
✓ Branch 5 taken 4076 times.
 2356463 flt_ (u32, x, 1, nx + 1) g[b][x].w = g[x][b].w = 0;
106
2/2
✓ Branch 2 taken 2020178 times.
✓ Branch 3 taken 4076 times.
 2024254 flt_ (u32, x, 1, n + 1) flo_from[b][x] = 0;
107
2/2
✓ Branch 6 taken 30824 times.
✓ Branch 7 taken 4076 times.
 34900 for (auto xs : flo[b]) {
108
2/2
✓ Branch 0 taken 17192469 times.
✓ Branch 1 taken 30824 times.
 17223293 flt_ (u32, x, 1, nx + 1)
109
6/6
✓ Branch 2 taken 14801482 times.
✓ Branch 3 taken 2390987 times.
✓ Branch 10 taken 613899 times.
✓ Branch 11 taken 14187583 times.
✓ Branch 12 taken 3004886 times.
✓ Branch 13 taken 14187583 times.
 17192469 if (g[b][x].w == 0 || e_delta(g[xs][x]) < e_delta(g[b][x])) g[b][x] = g[xs][x], g[x][b] = g[x][xs];
110
2/2
✓ Branch 0 taken 15351770 times.
✓ Branch 1 taken 30824 times.
 15382594 flt_ (u32, x, 1, n + 1)
111
2/2
✓ Branch 2 taken 1187458 times.
✓ Branch 3 taken 14164312 times.
 15351770 if (flo_from[xs][x]) flo_from[b][x] = xs;
112 }
113 4076 set_slack(b);
114 4076 }
115 3391 CEXP void expand_blossom(u32 b) NE {
116
2/2
✓ Branch 7 taken 27399 times.
✓ Branch 8 taken 3391 times.
 30790 for (auto t : flo[b]) set_st(t, t);
117 3391 cu32 xr = flo_from[b][g[b][par[b]].u], pr = get_pr(b, xr);
118
2/2
✓ Branch 0 taken 4685 times.
✓ Branch 1 taken 3391 times.
 8076 for (u32 i = 0; i < pr; i += 2) {
119 4685 u32 xs = flo[b][i], xns = flo[b][i + 1];
120 4685 par[xs] = g[xns][xs].u, s[xs] = 1, s[xns] = slack[xs] = slack[xns] = 0, q_push(xns);
121 }
122 3391 s[xr] = 1, par[xr] = par[b];
123
2/2
✓ Branch 2 taken 14638 times.
✓ Branch 3 taken 3391 times.
 18029 flt_ (u32, i, pr + 1, (u32)flo[b].size()) {
124 14638 u32 xs = flo[b][i];
125 14638 s[xs] = -1_u32, set_slack(xs);
126 }
127 3391 st[b] = 0;
128 3391 }
129 340094 bool on_found_edge(TIFA CR e) NE {
130 340094 cu32 u = st[e.u], v = st[e.v];
131
2/2
✓ Branch 1 taken 130852 times.
✓ Branch 2 taken 209242 times.
 340094 if (!~s[v]) {
132 130852 par[v] = e.u, s[v] = 1, slack[v] = 0;
133 130852 u32 nu = st[match[v]];
134 130852 s[nu] = slack[nu] = 0, q_push(nu);
135
2/2
✓ Branch 1 taken 7619 times.
✓ Branch 2 taken 201623 times.
 209242 } else if (!s[v]) {
136
2/2
✓ Branch 1 taken 3543 times.
✓ Branch 2 taken 4076 times.
 7619 if (u32 anc = lca(u, v); !anc) {
137 3543 augment(u, v), augment(v, u);
138 3543 return true;
139 4076 } else add_blossom(u, anc, v);
140 }
141 336551 return false;
142 }
143 3567 bool matching(T inf) NE {
144 3567 q = std::queue<u32>();
145
2/2
✓ Branch 0 taken 1758905 times.
✓ Branch 1 taken 3567 times.
 1762472 flt_ (u32, x, 1, nx + 1)
146
6/6
✓ Branch 4 taken 1716541 times.
✓ Branch 5 taken 42364 times.
✓ Branch 7 taken 944183 times.
✓ Branch 8 taken 772358 times.
✓ Branch 9 taken 944183 times.
✓ Branch 10 taken 814722 times.
 1758905 if (s[x] = -1_u32, slack[x] = 0; st[x] == x && !match[x]) par[x] = s[x] = 0, q_push(x);
147
2/2
✓ Branch 1 taken 3555 times.
✓ Branch 2 taken 12 times.
 3567 if (q.empty()) return false;
148 23131 while (true) {
149
2/2
✓ Branch 1 taken 1084561 times.
✓ Branch 2 taken 26632 times.
 1111193 while (!q.empty()) {
150 1084561 cu32 u = q.front();
151
1/2
✗ Branch 3 not taken.
✓ Branch 4 taken 1084561 times.
 1084561 if (q.pop(); s[st[u]] == 1) continue;
152
2/2
✓ Branch 0 taken 541101555 times.
✓ Branch 1 taken 1084507 times.
 542186062 flt_ (u32, v, 1, n + 1)
153
6/6
✓ Branch 2 taken 266454373 times.
✓ Branch 3 taken 274647182 times.
✓ Branch 6 taken 261894793 times.
✓ Branch 7 taken 4559580 times.
✓ Branch 8 taken 261894793 times.
✓ Branch 9 taken 279206762 times.
 541101555 if (g[u][v].w > 0 && st[u] != st[v]) {
154
2/2
✓ Branch 3 taken 310351 times.
✓ Branch 4 taken 261584442 times.
 261894793 if (!e_delta(g[u][v])) {
155
2/2
✓ Branch 3 taken 54 times.
✓ Branch 4 taken 310297 times.
 313852 if (on_found_edge(g[u][v])) return true;
156 261584442 } else upd_slack(u, st[v]);
157 }
158 }
159 26632 T d = inf;
160
2/2
✓ Branch 0 taken 840503 times.
✓ Branch 1 taken 26632 times.
 867135 flt_ (u32, b, n + 1, nx + 1)
161
6/6
✓ Branch 1 taken 6955 times.
✓ Branch 2 taken 833548 times.
✓ Branch 4 taken 3780 times.
✓ Branch 5 taken 3175 times.
✓ Branch 6 taken 3780 times.
✓ Branch 7 taken 836723 times.
 840503 if (st[b] == b && s[b] == 1) d = min(d, lab[b] / 2);
162
2/2
✓ Branch 0 taken 14098189 times.
✓ Branch 1 taken 26632 times.
 14124821 flt_ (u32, x, 1, nx + 1)
163
6/6
✓ Branch 1 taken 11821988 times.
✓ Branch 2 taken 2276201 times.
✓ Branch 4 taken 11247601 times.
✓ Branch 5 taken 574387 times.
✓ Branch 6 taken 11247601 times.
✓ Branch 7 taken 2850588 times.
 14098189 if (st[x] == x && slack[x]) {
164
2/2
✓ Branch 1 taken 4232524 times.
✓ Branch 2 taken 7015077 times.
 11247601 if (!~s[x]) d = min(d, e_delta(g[slack[x]][x]));
165
2/2
✓ Branch 1 taken 5156825 times.
✓ Branch 2 taken 1858252 times.
 7015077 else if (!s[x]) d = min(d, e_delta(g[slack[x]][x]) / 2);
166 }
167
2/2
✓ Branch 0 taken 13254251 times.
✓ Branch 1 taken 26620 times.
 13280871 flt_ (u32, u, 1, n + 1) {
168
2/2
✓ Branch 2 taken 5828229 times.
✓ Branch 3 taken 7426022 times.
 13254251 if (!s[st[u]]) {
169
2/2
✓ Branch 1 taken 12 times.
✓ Branch 2 taken 5828217 times.
 5828229 if (lab[u] <= d) return false;
170 5828217 lab[u] -= d;
171
2/2
✓ Branch 2 taken 2955399 times.
✓ Branch 3 taken 4470623 times.
 7426022 } else if (s[st[u]] == 1) lab[u] += d;
172 }
173
2/2
✓ Branch 0 taken 840499 times.
✓ Branch 1 taken 26620 times.
 867119 flt_ (u32, b, n + 1, nx + 1)
174
8/8
✓ Branch 1 taken 6951 times.
✓ Branch 2 taken 833548 times.
✓ Branch 4 taken 5810 times.
✓ Branch 5 taken 1141 times.
✓ Branch 6 taken 5810 times.
✓ Branch 7 taken 834689 times.
✓ Branch 9 taken 2031 times.
✓ Branch 10 taken 3779 times.
 840499 if (st[b] == b && ~s[b]) lab[b] += (!s[b] ? 1 : -1) * d * 2;
175 26620 q = std::queue<u32>();
176
2/2
✓ Branch 0 taken 13024451 times.
✓ Branch 1 taken 23131 times.
 13047582 flt_ (u32, x, 1, nx + 1)
177
9/10
✓ Branch 1 taken 10768148 times.
✓ Branch 2 taken 2256303 times.
✓ Branch 4 taken 10332436 times.
✓ Branch 5 taken 435712 times.
✓ Branch 8 taken 10332436 times.
✗ Branch 9 not taken.
✓ Branch 14 taken 29743 times.
✓ Branch 15 taken 10302693 times.
✓ Branch 16 taken 29743 times.
✓ Branch 17 taken 12994708 times.
 13024451 if (st[x] == x && slack[x] && st[slack[x]] != x && !e_delta(g[slack[x]][x]))
178
2/2
✓ Branch 4 taken 3489 times.
✓ Branch 5 taken 26254 times.
 29743 if (on_found_edge(g[slack[x]][x])) return true;
179
2/2
✓ Branch 0 taken 827537 times.
✓ Branch 1 taken 23131 times.
 850668 flt_ (u32, b, n + 1, nx + 1)
180
8/8
✓ Branch 1 taken 6618 times.
✓ Branch 2 taken 820919 times.
✓ Branch 4 taken 3837 times.
✓ Branch 5 taken 2781 times.
✓ Branch 7 taken 3391 times.
✓ Branch 8 taken 446 times.
✓ Branch 9 taken 3391 times.
✓ Branch 10 taken 824146 times.
 827537 if (st[b] == b && s[b] == 1 && !lab[b]) expand_blossom(b);
181 }
182 return false;
183 }
184 };
185
186 } // namespace tifa_libs
187