GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 58 / 0 / 58
Functions: 100.0% 10 / 0 / 10
Branches: 96.7% 58 / 0 / 60
src/graph/nf/dinic/lib.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "../../../util/alias/others/lib.hpp"
4
5 namespace tifa_libs {
6
7 template <class T = u32>
8 class dinic {
9 struct TIFA {
10 u32 to;
11 T w;
12 u32 inv;
13 };
14 cu32 n;
15
16 public:
17 vvec<TIFA> e;
18 vecu dep, cur;
19
20 645 CEXPE dinic(u32 n) NE : n{n}, e(n) {}
21
22 14084034 CEXP pttu add(u32 u, u32 v, T w, T rw = 0) NE {
23 14084034 cu32 lstu = (u32)e[u].size(), lstv = (u32)e[v].size();
24 14084034 e[u].push_back({v, w, lstv}), e[v].push_back({u, rw, lstu});
25 14084034 return {u, e[u].size() - 1};
26 }
27 template <class EW = u64>
28 7604 EW get(u32 s, u32 t) NE {
29 7604 EW ret = 0, flow;
30
4/4
unsigned long tifa_libs::dinic<unsigned int>::get<unsigned long>(unsigned int, unsigned int):
✓ Branch 1 taken 2525 times.
✓ Branch 2 taken 124 times.
unsigned long tifa_libs::dinic<unsigned long>::get<unsigned long>(unsigned int, unsigned int):
✓ Branch 1 taken 22616 times.
✓ Branch 2 taken 7480 times.
 32745 while (bfs(s, t))
31
4/4
unsigned long tifa_libs::dinic<unsigned int>::get<unsigned long>(unsigned int, unsigned int):
✓ Branch 2 taken 2525 times.
✓ Branch 3 taken 2525 times.
unsigned long tifa_libs::dinic<unsigned long>::get<unsigned long>(unsigned int, unsigned int):
✓ Branch 2 taken 22616 times.
✓ Branch 3 taken 22616 times.
 50282 while ((flow = dfs<EW>(s, t))) ret += flow;
32 7604 return ret;
33 }
34
35 private:
36 32745 bool bfs(u32 s, u32 t) NE {
37 32745 dep = vecu(n, 0), dep[s] = 1;
38 65490 std::queue<u32> q({s});
39
4/4
tifa_libs::dinic<unsigned int>::bfs(unsigned int, unsigned int):
✓ Branch 1 taken 397594993 times.
✓ Branch 2 taken 2649 times.
tifa_libs::dinic<unsigned long>::bfs(unsigned int, unsigned int):
✓ Branch 1 taken 2527615 times.
✓ Branch 2 taken 30096 times.
 400155353 while (!q.empty()) {
40 400122608 cu32 u = q.front();
41
4/4
tifa_libs::dinic<unsigned int>::bfs(unsigned int, unsigned int):
✓ Branch 7 taken 1772647295 times.
✓ Branch 8 taken 397594993 times.
tifa_libs::dinic<unsigned long>::bfs(unsigned int, unsigned int):
✓ Branch 7 taken 73930487 times.
✓ Branch 8 taken 2527615 times.
 2246700390 for (q.pop(); auto v : e[u])
42
12/12
tifa_libs::dinic<unsigned int>::bfs(unsigned int, unsigned int):
✓ Branch 1 taken 851959055 times.
✓ Branch 2 taken 920688240 times.
✓ Branch 3 taken 397592344 times.
✓ Branch 4 taken 454366711 times.
✓ Branch 5 taken 397592344 times.
✓ Branch 6 taken 1375054951 times.
tifa_libs::dinic<unsigned long>::bfs(unsigned int, unsigned int):
✓ Branch 1 taken 3135949 times.
✓ Branch 2 taken 70794538 times.
✓ Branch 3 taken 2497519 times.
✓ Branch 4 taken 638430 times.
✓ Branch 5 taken 2497519 times.
✓ Branch 6 taken 71432968 times.
 1846577782 if (!dep[v.to] && v.w) dep[v.to] = dep[u] + 1, q.push(v.to);
43 }
44 32745 cur = vecu(n, 0);
45 32745 return dep[t];
46 32745 }
47 template <class EW>
48 220213151 CEXP EW dfs(u32 u, u32 t, T lim = std::numeric_limits<T>::max()) NE {
49
6/8
unsigned long tifa_libs::dinic<unsigned int>::dfs<unsigned long>(unsigned int, unsigned int, unsigned int):
✓ Branch 0 taken 214779895 times.
✓ Branch 1 taken 2441021 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 214779895 times.
unsigned long tifa_libs::dinic<unsigned long>::dfs<unsigned long>(unsigned int, unsigned int, unsigned long):
✓ Branch 0 taken 2378011 times.
✓ Branch 1 taken 614224 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 2378011 times.
 220213151 if (u == t || lim == 0) return (EW)lim;
50 217157906 EW ret = 0;
51
4/4
unsigned long tifa_libs::dinic<unsigned int>::dfs<unsigned long>(unsigned int, unsigned int, unsigned int):
✓ Branch 3 taken 911891263 times.
✓ Branch 4 taken 206899666 times.
unsigned long tifa_libs::dinic<unsigned long>::dfs<unsigned long>(unsigned int, unsigned int, unsigned long):
✓ Branch 3 taken 53158949 times.
✓ Branch 4 taken 1783733 times.
 1173733611 for (u32& i = cur[u]; i < e[u].size(); ++i)
52
12/12
unsigned long tifa_libs::dinic<unsigned int>::dfs<unsigned long>(unsigned int, unsigned int, unsigned int):
✓ Branch 4 taken 226184570 times.
✓ Branch 5 taken 685706693 times.
✓ Branch 6 taken 217215866 times.
✓ Branch 7 taken 8968704 times.
✓ Branch 8 taken 217215866 times.
✓ Branch 9 taken 694675397 times.
unsigned long tifa_libs::dinic<unsigned long>::dfs<unsigned long>(unsigned int, unsigned int, unsigned long):
✓ Branch 4 taken 3024249 times.
✓ Branch 5 taken 50134700 times.
✓ Branch 6 taken 2947003 times.
✓ Branch 7 taken 77246 times.
✓ Branch 8 taken 2947003 times.
✓ Branch 9 taken 50211946 times.
 965050212 if (auto v = e[u][i]; dep[v.to] == dep[u] + 1 && v.w) {
53
4/4
unsigned long tifa_libs::dinic<unsigned int>::dfs<unsigned long>(unsigned int, unsigned int, unsigned int):
✓ Branch 2 taken 10322047 times.
✓ Branch 3 taken 206893819 times.
unsigned long tifa_libs::dinic<unsigned long>::dfs<unsigned long>(unsigned int, unsigned int, unsigned long):
✓ Branch 2 taken 1367010 times.
✓ Branch 3 taken 1579993 times.
 220162869 if (EW flow = dfs<EW>(v.to, t, min(v.w, lim)); flow) {
54
4/4
unsigned long tifa_libs::dinic<unsigned int>::dfs<unsigned long>(unsigned int, unsigned int, unsigned int):
✓ Branch 6 taken 7880229 times.
✓ Branch 7 taken 2441818 times.
unsigned long tifa_libs::dinic<unsigned long>::dfs<unsigned long>(unsigned int, unsigned int, unsigned long):
✓ Branch 6 taken 594278 times.
✓ Branch 7 taken 772732 times.
 11689057 if (e[u][i].w -= (T)flow, e[v.to][e[u][i].inv].w += (T)flow, ret += flow, lim -= (T)flow; !lim) break;
55 208473812 } else dep[v.to] = 0;
56 }
57 217157906 return ret;
58 }
59 };
60
61 } // namespace tifa_libs
62