Submission details
Task:Internet connection
Sender:sspilsbury
Submission time:2020-09-19 14:43:01 +0300
Language:C++ (C++11)
Status:COMPILE ERROR

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:10:3: error: 'memset' was not declared in this scope
   memset(M, 0, sizeof(unsigned long) * 100 * 100);
   ^~~~~~
input/code.cpp:10:3: note: suggested alternative: 'wmemset'
   memset(M, 0, sizeof(unsigned long) * 100 * 100);
   ^~~~~~
   wmemset

Code

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

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

  memset(M, 0, sizeof(unsigned long) * 100 * 100);
  memset(R, 0, sizeof(unsigned long) * 100 * 100);

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

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

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

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

  int flow = 0;

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

  while (true) {
    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;
}