fork(2) download
  1. #pragma GCC optimize(3)
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. const int MAXN = 1205;
  7. template <int MAXN, class T = int> struct HLPP {
  8. const T INF = numeric_limits<T>::max();
  9. struct edge {
  10. int to, rev;
  11. T f;
  12. };
  13. int s = MAXN - 1, t = MAXN - 2;
  14. vector<edge> edges[MAXN];
  15. vector<int> lst[MAXN], gap[MAXN];
  16. T excess[MAXN];
  17. int highest, height[MAXN], cnt[MAXN];
  18. void addEdge(int from, int to, int f, bool isDirected = true) {
  19. edges[from].push_back({to, (int)edges[to].size(), f});
  20. edges[to].push_back({from, (int)edges[from].size() - 1, isDirected ? 0 : f});
  21. }
  22. void updHeight(int v, int nh) {
  23. if (height[v] != MAXN)
  24. cnt[height[v]]--;
  25. height[v] = nh;
  26. if (nh == MAXN)
  27. return;
  28. cnt[nh]++, highest = nh;
  29. gap[nh].push_back(v);
  30. if (excess[v] > 0) {
  31. gap[nh].push_back(v);
  32. lst[nh].push_back(v);
  33. }
  34. }
  35. void globalRelabel() {
  36. fill(begin(height), end(height), MAXN);
  37. fill(begin(cnt), end(cnt), 0);
  38. for (int i = 0; i < MAXN; i++) {
  39. lst[i].clear();
  40. gap[i].clear();
  41. }
  42. height[t] = 0;
  43. queue<int> q({t});
  44. while (!q.empty()) {
  45. int v = q.front();
  46. q.pop();
  47. for (auto &e : edges[v]) {
  48. if (height[e.to] != MAXN || edges[e.to][e.rev].f <= 0)
  49. continue;
  50. updHeight(e.to, height[v] + 1);
  51. q.push(e.to);
  52. }
  53. highest = height[v];
  54. }
  55. }
  56. void push(int v, edge &e) {
  57. if (excess[e.to] == 0)
  58. lst[height[e.to]].push_back(e.to);
  59. T df = min(excess[v], e.f);
  60. e.f -= df, edges[e.to][e.rev].f += df;
  61. excess[v] -= df, excess[e.to] += df;
  62. }
  63. int work = 0;
  64. void discharge(int v) {
  65. int nh = MAXN;
  66. for (auto &e : edges[v]) {
  67. if (e.f <= 0)
  68. continue;
  69. if (height[v] == height[e.to] + 1) {
  70. push(v, e);
  71. if (excess[v] <= 0)
  72. return;
  73. } else
  74. nh = min(nh, height[e.to] + 1);
  75. }
  76. work++;
  77. if (cnt[height[v]] > 1)
  78. updHeight(v, nh);
  79. else {
  80. for (int i = height[v]; i <= highest; i++) {
  81. for (auto j : gap[i])
  82. updHeight(j, MAXN);
  83. gap[i].clear();
  84. }
  85. }
  86. }
  87. T calc(int n) {
  88. fill(begin(excess), end(excess), 0);
  89. excess[s] = INF, excess[t] = -INF;
  90. globalRelabel();
  91. for (auto &e : edges[s])
  92. push(s, e);
  93. for (; highest >= 0; highest--) {
  94. while (!lst[highest].empty()) {
  95. int v = lst[highest].back();
  96. lst[highest].pop_back();
  97. discharge(v);
  98. if (work > 4 * n) {
  99. globalRelabel();
  100. work = 0;
  101. }
  102. }
  103. }
  104. return excess[t] + INF;
  105. }
  106. };
  107.  
  108. HLPP<MAXN, long long> hlpp;
  109.  
  110. inline void scan_int(int *p) {
  111. static char c;
  112. while ((c = getchar_unlocked()) < '0')
  113. ; // just to be safe
  114. for (*p = c - '0'; (c = getchar_unlocked()) >= '0'; *p = *p * 10 + c - '0')
  115. ;
  116. }
  117. signed main() {
  118. ios::sync_with_stdio(0);
  119. cin.tie(0);
  120. int n, m;
  121. scan_int(&n), scan_int(&m);
  122. // cin >> n >> m;
  123. int s = 1, t = n;
  124. scan_int(&s), scan_int(&t);
  125. // cin >> s >> t;
  126. for (int i = 0, u, v, f; i < m; ++i) {
  127. scan_int(&u), scan_int(&v), scan_int(&f);
  128. // cin >> u >> v >> f;
  129. hlpp.addEdge(u, v, f, true);
  130. }
  131. hlpp.s = s, hlpp.t = t;
  132. cout << hlpp.calc(n) << endl;
  133. }
  134.  
Success #stdin #stdout 0.01s 5452KB
stdin
111 224 111 16
1 56 10000007
67 1 1000000000
57 1 1000000000
111 1 1000000000
111 1 1000000000
2 57 10000006
68 2 1000000000
58 2 1000000000
111 2 1000000000
56 2 1000000000
3 58 10000001
69 3 1000000000
59 3 1000000000
111 3 1000000000
57 3 1000000000
5 60 10000006
71 5 1000000000
61 5 1000000000
111 5 1000000000
59 5 1000000000
6 61 10000002
72 6 1000000000
62 6 1000000000
111 6 1000000000
60 6 1000000000
7 62 10000008
73 7 1000000000
63 7 1000000000
111 7 1000000000
61 7 1000000000
8 63 10000002
74 8 1000000000
64 8 1000000000
111 8 1000000000
62 8 1000000000
9 64 10000001
75 9 1000000000
65 9 1000000000
111 9 1000000000
63 9 1000000000
11 66 10000002
77 11 1000000000
111 11 1000000000
111 11 1000000000
65 11 1000000000
12 67 10000003
78 12 1000000000
68 12 1000000000
56 12 1000000000
111 12 1000000000
13 68 10000008
79 13 1000000000
69 13 1000000000
57 13 1000000000
67 13 1000000000
14 69 10000007
80 14 1000000000
70 14 1000000000
58 14 1000000000
68 14 1000000000
15 70 10000002
81 15 1000000000
71 15 1000000000
59 15 1000000000
69 15 1000000000
82 16 1000000000
72 16 1000000000
60 16 1000000000
70 16 1000000000
17 72 10000009
83 17 1000000000
73 17 1000000000
61 17 1000000000
71 17 1000000000
18 73 10000002
84 18 1000000000
74 18 1000000000
62 18 1000000000
72 18 1000000000
19 74 10000003
85 19 1000000000
75 19 1000000000
63 19 1000000000
73 19 1000000000
20 75 10000008
86 20 1000000000
76 20 1000000000
64 20 1000000000
74 20 1000000000
21 76 10000003
87 21 1000000000
77 21 1000000000
65 21 1000000000
75 21 1000000000
22 77 10000009
88 22 1000000000
111 22 1000000000
66 22 1000000000
76 22 1000000000
23 78 10000003
89 23 1000000000
79 23 1000000000
67 23 1000000000
111 23 1000000000
24 79 10000006
90 24 1000000000
80 24 1000000000
68 24 1000000000
78 24 1000000000
25 80 10000009
91 25 1000000000
81 25 1000000000
69 25 1000000000
79 25 1000000000
27 82 10000007
93 27 1000000000
83 27 1000000000
71 27 1000000000
81 27 1000000000
28 83 10000002
94 28 1000000000
84 28 1000000000
72 28 1000000000
82 28 1000000000
29 84 10000004
95 29 1000000000
85 29 1000000000
73 29 1000000000
83 29 1000000000
30 85 10000004
96 30 1000000000
86 30 1000000000
74 30 1000000000
84 30 1000000000
31 86 10000002
97 31 1000000000
87 31 1000000000
75 31 1000000000
85 31 1000000000
32 87 10000003
98 32 1000000000
88 32 1000000000
76 32 1000000000
86 32 1000000000
33 88 10000004
99 33 1000000000
111 33 1000000000
77 33 1000000000
87 33 1000000000
34 89 10000008
100 34 1000000000
90 34 1000000000
78 34 1000000000
111 34 1000000000
37 92 10000001
103 37 1000000000
93 37 1000000000
81 37 1000000000
91 37 1000000000
38 93 10000006
104 38 1000000000
94 38 1000000000
82 38 1000000000
92 38 1000000000
39 94 10000004
105 39 1000000000
95 39 1000000000
83 39 1000000000
93 39 1000000000
40 95 10000006
106 40 1000000000
96 40 1000000000
84 40 1000000000
94 40 1000000000
42 97 10000003
108 42 1000000000
98 42 1000000000
86 42 1000000000
96 42 1000000000
43 98 10000008
109 43 1000000000
99 43 1000000000
87 43 1000000000
97 43 1000000000
46 101 10000009
111 46 1000000000
102 46 1000000000
90 46 1000000000
100 46 1000000000
47 102 10000007
111 47 1000000000
103 47 1000000000
91 47 1000000000
101 47 1000000000
48 103 10000005
111 48 1000000000
104 48 1000000000
92 48 1000000000
102 48 1000000000
49 104 10000005
111 49 1000000000
105 49 1000000000
93 49 1000000000
103 49 1000000000
51 106 10000001
111 51 1000000000
107 51 1000000000
95 51 1000000000
105 51 1000000000
53 108 10000005
111 53 1000000000
109 53 1000000000
97 53 1000000000
107 53 1000000000
54 109 10000001
111 54 1000000000
110 54 1000000000
98 54 1000000000
108 54 1000000000
55 110 10000004
111 55 1000000000
111 55 1000000000
99 55 1000000000
109 55 1000000000

stdout
20000008