LiveArchive 7226 Coin Swap

問題
https://icpcarchive.ecs.baylor.edu/external/72/7226.pdf

白または黒の何れかが塗られたノードを持つグラフがある。
はじめ、白または黒のコインが、ノードの色の数と同じ数だけバラバラのノードの1つずつ置かれている。
コインを隣接するノードのコインと入れ替えるのにコスト1消費する。
ノードの色とコインの色が一致するように入れ替える最小回数を求めよ。

解答
色の数が一致しているので、白または黒の何れか一方についてのみ考えれば十分。例えば、黒についてのみ考える。
また、入れ替える操作を両方のコインを考慮せず片方だけ考慮するように考える。つまり、あるコインを移動させるコストが1と考える。
まとめると、いずれかの黒のコインをいずれかの黒のノードに送る最小コストを求める問題である。
コインの移動を流量1のフローとみて、移動のコストを1と考える。はじめのコインの位置は、ソースと直に繋がるノードと考え、最終的なコインの到達位置（つまり黒色のノード）からはシンクに直に繋げる。
ソースからシンクに黒のコイン(ノード)の数だけの流量を流す。最小費用流問題である。
無向グラフなので、辺を張るときに両側から張ることに気をつける。蟻本で言うところのadd_edge()をグラフの各辺については2回行う。

なお、ダイクストラをN回実行する方が計算量が見積もれる上にICPCでは簡単に実装できる。

typedef long long ll;
int const inf = 1<<29;

int N, M;

namespace flow {

struct edge {
  int to, cap, cost, rev;
  edge(int t, int ca, int co, int r) : to(t), cap(ca), cost(co), rev(r) {}
};

struct primal_dual {

  vector<vector<edge>> G;
  vector<int> h;
  vector<int> dist;
  vector<int> prevv, preve;

  primal_dual(int V) : G(V), h(V), dist(V), prevv(V), preve(V) {}

  void add_edge(int from, int to, int cap, int cost) {
    G[from].emplace_back(to, cap, cost, G[to].size());
    G[to].emplace_back(from, 0, -cost, G[from].size()-1);
  }

  int min_cost_flow(int s, int t, int f) {
    int ret = 0;
    fill(h.begin(), h.end(), 0);
    while(f > 0) {
      typedef pair<int, int> P;
      priority_queue<P, vector<P>, greater<P>> pq;
      fill(dist.begin(), dist.end(), inf);
      dist[s] = 0;
      pq.emplace(0, s);
      while(!pq.empty()) {
        P p = pq.top(); pq.pop();
        int v = p.second;
        if(dist[v] < p.first) { continue; }
        for(int i=0; i<G[v].size(); i++) {
          auto& e = G[v][i];
          if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
            dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
            prevv[e.to] = v;
            preve[e.to] = i;
            pq.emplace(dist[e.to], e.to);
          }
        }
      }

      if(dist[t] == inf) { return -1; }
      for(int i=0; i<h.size(); i++) h[i] += dist[i];

      int d = f;
      for(int i=t; i!=s; i=prevv[i]) {
        d = min(d, G[prevv[i]][preve[i]].cap);
      }
      f -= d;
      ret += d * h[t];
      for(int i=t; i!=s; i=prevv[i]) {
        auto& e = G[prevv[i]][preve[i]];
        e.cap -= d;
        G[i][e.rev].cap += d;
      }
    }
    return ret;
  }

};

}

int main() {

  int T; cin >> T;
  rep(_, T) {
    cin >> N >> M;
    flow::primal_dual pd(N+2);
    const int SRC = N, SINK = N+1;
    rep(i, M) {
      int a, b; cin >> a >> b;
      a --, b --;
      pd.add_edge(a, b, inf, 1);
      pd.add_edge(b, a, inf, 1);
    }
    rep(i, N) {
      int c; cin >> c;
      if(c) pd.add_edge(i, SINK, 1, 0);
    }

    int f = 0;
    rep(i, N) {
      int c; cin >> c;
      if(c) pd.add_edge(SRC, i, 1, 0), f ++;
    }

    cout << pd.min_cost_flow(SRC, SINK, f) << endl;
  }
  
  return 0;
}