AtCoder Library Practice Contest | E - MinCostFlow

問題

https://atcoder.jp/contests/practice2/tasks/practice2_e

解法

入力例1で考える。

($k / 0$は辺の最大フローが$k$でコストは$0$ということを表す)

上記のように前段で赤色の行ごとのパイプと後段で青色の列ごとのパイプがあるとする。
スタートの頂点$S$からゴールの頂点$G$まで各パイプが$K$のフローがコスト$0$で通ることができ、マスの頂点を通ったときに最大のフローが$1$としコストがマスの値とすると、最大フロー$K * N$(K * N以下でも可)を流したときにフローが流れているマスの合計の最大を求める問題である。

最小費用流の問題と似ているが以下の点が異なる。

1. 費用を最小にするのではなく最大にしたい
2. 必ずしもすべてのフローを流す必要はない。フローがなんであれ最大のコストにしたい。

(1) に関してはマスの最大値をマスの値から引くことで、最大値を最小値に変換することで最小費用流の問題に置き換えれる。

(2) に関して考える。入力例2で先程の図のグラフは以下のように単純化して表せる。

(ここではマスの最大値を$100$としている)

上記のように$S$から$G$まで最大フローが無限大でコストがマスの最大値のものを配置することによりマスに流れないフローの場合も表すことができ(2)の場合の最小のコストを求めることができる。

入力例2のときに、各行・列のマスを2つづつ選ぶ必要がある場合は以下の選択になってしまう。

42
XX.
.XX
X.X

ここで$S$から$G$に先程のパスを足すことによりマスへの流入フローが任意の場合でマス内での最小コストを求めることができる。

コード

実装時のTips

• AtCoder Libraryのmcf_graphを使います

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  ll mx = 1e9;
  ll n, k;
  cin >> n >> k;
  ll m = 2 * n + 2;
  ll s = 2 * n;
  ll g = s + 1;
  mcf_graph<ll, ll> graph(m);
  for (int i = 0; i < n; i++) {
    graph.add_edge(s, i, k, 0);
    graph.add_edge(n + i, g, k, 0);
  }
  vector<vector<ll>> a(n, vector<ll>(n));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      // 最小費用流なので, 大きい値ほど小さくしておく
      cin >> a[i][j];
      a[i][j] = mx - a[i][j];
      graph.add_edge(i, n + j, 1, a[i][j]);
    }
  }
  graph.add_edge(s, g, mx, mx);
  ll ans = 0;
  auto r = graph.flow(s, g, n * k);
  vector<vector<char>> result(n, vector<char>(n, '.'));
  for (auto edge : graph.edges()) {
    if (edge.from == s || edge.to == g || edge.flow == 0) continue;
    int i = edge.from;
    int j = edge.to - n;
    result[i][j] = 'X';
    ans += mx - edge.cost;
  }
  cout << ans << endl;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cout << result[i][j];
    }
    cout << endl;
  }
}

参考

https://note.com/nullkara/n/n700f2f2753c9