Function test_rand

code/graph/bipartite_matching.test.cpp:3–43

#include "../code/graph/dinic.cpp"

void test_rand(int N, int M) {
  adj = new vi[N];

  done = new bool[N];
  memset(done, 0, sizeof(bool) * N);

  owner = new int[M];
  memset(owner, -1, sizeof(int) * M);

  flow_network g(N + M + 2);

  int SOURCE = N + M;
  int SINK = N + M + 1;

  for(int i = 0; i < N; i++) {
    g.add_edge(SOURCE, i, 1, 0);
    for(int j = 0; j < M; j++) {
      if(rng() % 2) {
        // cout << i << " -> " << j << endl;
        g.add_edge(i, N + j, 1, 0);
        adj[i].push_back(j);
      }
    }
  }

  for(int j = 0; j < M; j++) {
    g.add_edge(j + N, SINK, 1, 0);
  }

  int sum = 0;
  for(int i = 0; i < N; ++i) {
    memset(done, 0, sizeof(bool) * N);
    sum += alternating_path(i);
  }

  assert_equal(g.max_flow(SOURCE, SINK), sum);

  delete[] adj;
  delete[] done;
  delete[] owner;
}

void test_1() {
  int N = 3, M = 3;