🐕

# AtCoder Library Practice Contest | D - Maxflow

2020/10/25に公開

## コード

``````#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) {
// 白マスをゴールと接続
continue;
}

// 黒マスをスタートと接続

// 黒マスと隣接する白マスを接続する
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;  // マスの番号
}
}
}
// 最大フローの計算
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;
}
}

``````