ハコの魔女 (AOJ 2313)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2313

問題

略

解法

解説参照。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <set>
#include <queue>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

typedef int Weight;

typedef set<Weight> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

void PrintMatrix(const Matrix &matrix) {
  REP(y, matrix.size()) {
    REP(x, matrix[0].size()) {
      printf("%d ", matrix[y][x]);
    }
    puts("");
  }
}

void AddEdge(Graph &g, Matrix &capacity, int from, int to) {
  g[from].insert(to);
  g[to].insert(from);
  capacity[from][to]++;
  capacity[to][from]++;
}

void EraseEdge(Graph &g, Matrix &capacity, int from, int to) {
  assert(capacity[from][to] == 1);
  assert(capacity[to][from] == 1);
  g[from].erase(to);
  g[to].erase(from);
  capacity[from][to]--;
  capacity[to][from]--;
}

bool visit[1100];
int DfsFlow(Graph &g, Matrix &capacity, int from, int target) {
  if (from == target) { return 1; }
  visit[from] = true;
  FORIT(it, g[from]) {
    int to = *it;
    if (visit[to] || capacity[from][to] == 0) { continue; }
    if (DfsFlow(g, capacity, to, target)) {
      capacity[from][to]--;
      capacity[to][from]++;
      return 1;
    }
  }
  return 0;
}

int n, m, q;
int main() {
  while (scanf("%d %d %d", &n, &m, &q) > 0) {
    Graph g(n);
    Matrix capacity(n, Array(n, 0));
    REP(i, m) {
      int from, to;
      int v = scanf("%d %d", &from, &to);
      assert(v == 2);
      from--; to--;
      AddEdge(g, capacity, from, to);
    }
    int flow = 0;
    while (true) {
      MEMSET(visit, false);
      if (DfsFlow(g, capacity, 0, n - 1) == 0) { break; }
      flow++;
    }
    REP(iter, q) {
      int type, from, to;
      int v = scanf("%d %d %d", &type, &from, &to);
      from--; to--;
      assert(v == 3);
      if (type == 1) {
        AddEdge(g, capacity, from, to);
        MEMSET(visit, false);
        flow += DfsFlow(g, capacity, 0, n - 1);
      } else {
        assert(capacity[from][to] + capacity[to][from] == 2);
        if (capacity[from][to] == 1) {
          EraseEdge(g, capacity, from, to);
        } else {
          MEMSET(visit, false);
          if (capacity[from][to] == 2) { swap(from, to); }
          if (DfsFlow(g, capacity, from, to) == 0) {
            MEMSET(visit, false);
            int nto1 = DfsFlow(g, capacity, n - 1, 0);
            assert(nto1);
            flow--;
            if (capacity[from][to] != 1) {
              MEMSET(visit, false);
              int ftot = DfsFlow(g, capacity, from, to);
              assert(ftot);
            }
          }
          capacity[from][to] = 1;
          capacity[to][from] = 1;
          EraseEdge(g, capacity, from, to);
        }
      }
      printf("%d\n", flow);
    }
  }
}