fork download
  1. /*
  2.   author : [ Godsent ]
  3.   created : 2025.07.30 02:03:23
  4. */
  5.  
  6. #include <bits/stdc++.h>
  7. #define el "\n"
  8. #define int long long
  9. #define lb lower_bound
  10. #define ub upper_bound
  11. #define fi first
  12. #define se second
  13. #define sz(x) ((int)(x).size())
  14. #define all(v) (v).begin(), (v).end()
  15. #define pb push_back
  16. #define prs(n) fixed << setprecision(n)
  17.  
  18. const int mod = 1e9 + 7;
  19. const int N = 1e3 + 5;
  20. const int INF = 1e18;
  21.  
  22. using namespace std;
  23.  
  24. vector<int> adj[N];
  25. int n, m, s, t, maxFlow, minCut;
  26. int lastVertexId[N];
  27. int f[N][N], c[N][N], d[N];
  28. int visited[N];
  29. vector<int> S;
  30. map<int,int> T;
  31.  
  32. void bfs() {
  33. queue<int> q;
  34. q.push(s);
  35. fill(d, d + n + 1, INF);
  36. d[s] = 0;
  37. while (!q.empty()) {
  38. int u = q.front();
  39. q.pop();
  40. for (auto &v : adj[u]) {
  41. if (d[v] != INF || c[u][v] - f[u][v] == 0) continue;
  42. d[v] = d[u] + 1;
  43. q.push(v);
  44. }
  45. }
  46. }
  47.  
  48. int increaseFlow(int u, int currDelta) {
  49. if (currDelta == 0) return 0;
  50. if (u == t) return currDelta;
  51.  
  52. for (; lastVertexId[u] < sz(adj[u]); lastVertexId[u]++) {
  53. int v = adj[u][lastVertexId[u]];
  54. if (d[v] != d[u] + 1 || c[u][v] - f[u][v] == 0) continue;
  55.  
  56. int delta = increaseFlow(v, min(currDelta, c[u][v] - f[u][v]));
  57. if (delta == 0) continue;
  58. f[u][v] += delta;
  59. f[v][u] -= delta;
  60. return delta;
  61. }
  62. return 0;
  63. }
  64.  
  65. void dfs(int u) {
  66. visited[u]++;
  67. for (auto &v : adj[u]) {
  68. if (!visited[v] && c[u][v] - f[u][v] > 0) dfs(v);
  69. }
  70. }
  71.  
  72. int findMinCut() {
  73. S.pb(s);
  74. T[t]++;
  75.  
  76. dfs(s);
  77.  
  78. for (int u = 1; u <= n; u++) {
  79. if (visited[u]) {
  80. for (auto &v : adj[u]) {
  81. if (!visited[v] && c[u][v] > 0) {
  82. minCut += c[u][v];
  83. }
  84. }
  85. }
  86. }
  87.  
  88. return minCut;
  89. }
  90.  
  91. signed main() {
  92. ios_base::sync_with_stdio(false);
  93. cin.tie(0);
  94. cout.tie(0);
  95.  
  96. #ifndef ONLINE_JUDGE
  97. freopen("test.inp", "r", stdin);
  98. freopen("test.out", "w", stdout);
  99. #endif
  100.  
  101. cin >> n >> m;
  102. s = 1;
  103. t = n;
  104.  
  105. for (int i = 1, u, v; i <= m; i++) {
  106. cin >> u >> v >> c[u][v];
  107. adj[u].pb(v);
  108. adj[v].pb(u);
  109. }
  110.  
  111. while (d[t] != INF) {
  112. bfs();
  113. for (int i = 1; i <= n; i++) lastVertexId[i] = 0;
  114. while (int delta = increaseFlow(s, INF)) maxFlow += delta;
  115. }
  116.  
  117. cout << maxFlow << el;
  118. cout << findMinCut() << el;
  119.  
  120. return 0;
  121. }
  122.  
Success #stdin #stdout 0.01s 5316KB
stdin
Standard input is empty
stdout
0
0