Download Speed

#include <bits/stdc++.h>
#define ll long long

template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
  os << "[";
  for (int i = 0; i < v.size(); ++i) {
    os << v[i];
    if (i != v.size() - 1)
      os << ", ";
  }
  os << "]";
  return os;
}

ll something(std::vector<std::unordered_map<ll, ll>> &costMap,
             std::vector<char> &checked, std::vector<ll> &path, ll start,
             ll wholeEnd) {
  path.push_back(start);
  if (start == wholeEnd) {
    return 1e15;
  }
  checked[start] = 1;

  for (const auto &[end, speed] : costMap[start]) {
    if (speed > 0 && !checked[end]) {
      ll ret = something(costMap, checked, path, end, wholeEnd);
      if (ret != -1) {
        return std::min(ret, costMap[start][end]);
      }
    }
  }
  path.pop_back();
  return -1;
}

ll bfs(std::vector<std::unordered_map<ll, ll>> &costMap, ll start, ll end,
       ll compCount, std::vector<ll> &path) {
  std::queue<ll> qq;
  std::vector<char> checked(compCount, 0);

  qq.push(start);
  checked[start] = 1;
  while (!qq.empty()) {
    ll cur = qq.front();
    qq.pop();

    for (const auto &[next, speed] : costMap[cur]) {
      if (!checked[next] && speed > 0) {
        qq.push(next);
        checked[next] = 1;
        path[next] = cur;
        if (next == end) {
          return 1;
        }
      }
    }
  }
  return checked[end];
}

int main() {
  ll compCount, conCount;
  std::cin >> compCount;
  std::cin >> conCount;

  //   std::cout << compCount << " " << conCount << std::endl;
  std::vector<std::unordered_map<ll, ll>> costMap(compCount,
                                                  std::unordered_map<ll, ll>());
  for (ll ii = 0; ii < conCount; ii++) {
    ll start, end, speed;
    // std::cout << start << " " << end << " " << speed << std::endl;
    std::cin >> start;
    std::cin >> end;
    std::cin >> speed;
    // if (end < start) {
    //   ll tmp = start;
    //   start = end;
    //   end = tmp;
    //   speed = -speed;
    // }

    if (costMap[start - 1].contains(end - 1)) {
      costMap[start - 1][end - 1] += speed;
    } else {
      costMap[start - 1][end - 1] = speed;
    }
    if (!costMap[end - 1].contains(start - 1)) {
      costMap[end - 1][start - 1] = 0;
    }
  }
  ll minSpeed = 0;
  ll throughtPut = 0;
  ll start = 0;
  ll end = compCount - 1;
  std::vector<char> checked(compCount, 0);
  while (1) {
    std::vector<ll> path(compCount, -1);
    ll success = bfs(costMap, start, end, compCount, path);
    if (!success) {
      break;
    }
    minSpeed = 1e15;

    ll ss = end;
    // std::cout << path << std::endl;
    while (ss != start) {
      minSpeed = std::min(minSpeed, costMap[path[ss]][ss]);
      ss = path[ss];
    }

    throughtPut += minSpeed;
    // std::cout << minSpeed << std::endl;

    ll vv = end;
    while (vv != start) {
      ll uu = path[vv];
      costMap[uu][vv] -= minSpeed;
      costMap[vv][uu] += minSpeed;
      vv = uu;
    }
  }
  std::cout << throughtPut << std::endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED