Internet connection

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <cstring>

int main(void) {
  unsigned long R[100][100];

  int m, n;
  std::cin >> n;
  std::cin >> m;

  memset(R, 0, sizeof(unsigned long) * n * n);

  // Populate the matrix
  for (int i = 0; i < m; ++i) {
    long x, y, z;
    std::cin >> x;
    std::cin >> y;
    std::cin >> z;

    R[x - 1][y - 1] = z;

    // std::cout << x << " " << y << " " << R[x][y] << std::endl;
  }

  unsigned long flow = 0;

  // std::cout << "Got input" << std::endl;

  for (int j = 0; j < n; ++j) {
    std::vector<bool> visited(n);
    std::vector<int> parent(n);
    std::queue<int> q;

    q.push(0);

    // Try to find a path from 0 to n - 1
    while (!q.empty()) {
      int node = q.front();
      q.pop();

      // std::cout << "visit " << node << std::endl;

      // Is this the target node? break the loop
      if (node == n - 1) {
        visited[node] = true;
        break;
      }

      // Have we already visited this node?
      if (visited[node] == true) {
        continue;
      }

      // We've now visited this node
      visited[node] = true;

      // We haven't visited this node. Enumerate the node's children
      // by reference to the residual matrix
      for (int i = 0; i < n; ++i) {
        // std::cout << "check " << node << " " << i << " " << R[node][i] << std::endl;
        if (R[node][i] > 0) {
          parent[i] = node;
          q.push(i);
        }
      }
    }

    // No more paths, break out
    if (!visited[n - 1]) {
      break;
    }

    // We have found a path. Update the residual matrix
    // and add the flow from this path to the next path
    int x = n - 1;
    unsigned long w = std::numeric_limits<unsigned long>::max();
    while (x != 0) {
      // std::cout << "Link " << parent[x] << " " << x << R[parent[x]][x] << std::endl;
      w = std::min(w, R[parent[x]][x]);
      x = parent[x];
    }

    // Now that we know the flow, we need to subtract that from the
    // residual matrix and add it back to the reverse edges
    x = n - 1;
    while (x != 0) {
      R[parent[x]][x] -= w;
      R[x][parent[x]] += w;
      x = parent[x];
    }

    // Add this flow to the maximum flow
    flow += w;
  }

  std::cout << flow << std::endl;
}

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: TIME LIMIT EXCEEDED

Test 22

Verdict: TIME LIMIT EXCEEDED