LelouchRiBritannia's blog

By LelouchRiBritannia, 6 years ago, In English

In 843E - Максимальный поток it is stated in the tutorial:

"For an each edge from original graph without any flow let's create a new edge with the same direction and c = INF carrying capacity. For every edge with a flow let's create two edges: the first one with the same direction and c = 1 capacity and the second edge with reversed direction and c = INF."

Why do I need the second edge with reversed direction and c=INF for the edge with flow? I know it affect the min-cut but I cannot find any specific example. In fact, in one of tourist submissions 29956114, he didn't add this edge and still get AC.

  int n, m, st, fin;
  scanf("%d %d %d %d", &n, &m, &st, &fin);
  st--; fin--;
  flow_graph <int> g(n, st, fin);
  for (int i = 0; i < m; i++) {
    scanf("%d %d %d", from + i, to + i, flag + i);
    from[i]--; to[i]--;
    if (flag[i] == 1) {
      g.add(from[i], to[i], 1, inf);
    } else {
      g.add(from[i], to[i], inf, 0);
    }
  }
  cout << g.max_flow() << endl;
  vector <bool> cut = g.min_cut();
  flow_graph <int> g2(n + 2, n, n + 1);
  for (int i = 0; i < m; i++) {
    if (!flag[i]) {
      continue;
    }
    g2.add(n, to[i], 1, 0);
    g2.add(from[i], n + 1, 1, 0);
    g2.add(from[i], to[i], inf - 2, 0);
  }
  g2.add(fin, st, inf, 0);
  g2.max_flow();