🐕
AtCoder Library Practice Contest | D - Maxflow
問題
考えたこと
左のように障害物がならんでいる。各(i,j)を市松模様で黒・白と右のように塗って番号をつける。タイルは1x2の大きさなので黒を必ず通る。
黒マスから隣接するマスへ辺をつないだ以下のようなグラフを考えると、最大のタイルの置き方はSからGまでの最大フロー問題を解けばいいことがわかる。
コード
#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() {
int n, m;
cin >> n >> m;
vector<string> mp(n);
for (int i = 0; i < n; i++) {
cin >> mp[i];
}
// mp[i][j] = i * M + j
// start: N * M, goal: N * M + 1
mf_graph<int> graph(n * m + 2);
int start = n * m;
int goal = n * m + 1;
vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mp[i][j] == '#') {
continue;
}
int u = i * m + j; // マスの番号
if (i % 2 == 0 ? j % 2 == 1 : j % 2 == 0) {
// 白マスをゴールと接続
graph.add_edge(u, goal, 1);
continue;
}
// 黒マスをスタートと接続
graph.add_edge(start, u, 1);
// 黒マスと隣接する白マスを接続する
for (auto direction : directions) {
int ni = i + direction.first;
int nj = j + direction.second;
if (ni < 0 || n <= ni || nj < 0 || m <= nj) {
continue;
}
if (mp[ni][nj] == '#') {
continue;
}
int v = ni * m + nj; // マスの番号
graph.add_edge(u, v, 1);
}
}
}
// 最大フローの計算
int maxFlow = graph.flow(start, goal);
for (auto edge : graph.edges()) {
if (edge.from == start || edge.to == goal) {
continue;
}
if (edge.flow == 0) {
continue;
}
int fi = edge.from / m;
int fj = edge.from % m;
int ti = edge.to / m;
int tj = edge.to % m;
if (fj == tj) {
// 縦
if (fi < ti) {
mp[fi][fj] = 'v';
mp[ti][tj] = '^';
} else {
mp[ti][tj] = 'v';
mp[fi][fj] = '^';
}
} else {
// 横
if (fj < tj) {
mp[fi][fj] = '>';
mp[ti][tj] = '<';
} else {
mp[ti][tj] = '>';
mp[fi][fj] = '<';
}
}
}
cout << maxFlow << endl;
for (int i = 0; i < n; i++) {
cout << mp[i] << endl;
}
}
Discussion