結果

問題 No.421 しろくろチョコレート
ユーザー boutarou
提出日時 2022-02-15 11:20:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 2,904 bytes
コンパイル時間 2,810 ms
コンパイル使用メモリ 205,104 KB
最終ジャッジ日時 2025-01-27 23:15:22
ジャッジサーバーID
(参考情報)
judge2 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 25 WA * 6 RE * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#line 1 "main.cpp"
#include <bits/stdc++.h>
#line 6 "/mnt/c/Users/araar/documents/kyopro/library/graph/FordFulkerson.cpp"
template <typename T>
class FordFulkerson {
public:
struct edge {
int to;
T cap;
int rev;
};
int n;
std::vector<std::vector<edge>> g;
std::vector<bool> used;
FordFulkerson(int n = 0)
: n(n), g(n), used(n) {
}
void add_edge(int from, int to, T cap) {
assert(0 <= from && from < n);
assert(0 <= to && to < n);
assert(0 <= cap);
g[from].push_back((edge){to, cap, int(g[to].size())});
g[to].push_back((edge){from, 0LL, int(g[from].size() - 1)});
}
T dfs(int v, int goal_v, T flow) {
if(v == goal_v) return flow;
used[v] = true;
for(int i = 0; i < (int)g[v].size(); i++) {
edge &e = g[v][i];
if(!used[e.to] && e.cap > 0) {
T next_flow = dfs(e.to, goal_v, std::min(flow, e.cap));
if(next_flow > 0) {
e.cap -= next_flow;
g[e.to][e.rev].cap += next_flow;
return next_flow;
}
}
}
return 0;
}
T max_flow(int s, int t, T ma = std::numeric_limits<T>::max()) {
assert(0 <= s && s < n);
assert(0 <= t && t < n);
T flow = 0;
while(1) {
used = std::vector<bool>(n, false);
T f = dfs(s, t, ma);
if(f == 0) return flow;
flow += f;
}
}
};
#line 3 "main.cpp"
using namespace std;
#define rep(i, n) for(int i = 0; i < int(n); i++)
using ll = long long;
using P = pair<int, int>;
int main() {
int h, w;
cin >> h >> w;
vector<string> s(h);
rep(i, h) cin >> s[i];
FordFulkerson<int> mcf_graph(h * w + 2);
int st = h * w, go = h * w + 1;
rep(i, h) {
rep(j, w) {
if(s[i][j] == '.') continue;
else if(s[i][j] == 'w') {
mcf_graph.add_edge(st, i * h + j, 1);
if(j + 1 < w && s[i][j + 1] != '.') mcf_graph.add_edge(i * h + j, i * h + j + 1, 1);
if(i + 1 < h && s[i + 1][j] != '.') mcf_graph.add_edge(i * h + j, (i + 1) * h + j, 1);
}
else {
mcf_graph.add_edge(i * h + j, go, 1);
if(j + 1 < w && s[i][j + 1] != '.') mcf_graph.add_edge(i * h + j + 1, i * h + j, 1);
if(i + 1 < h && s[i + 1][j] != '.') mcf_graph.add_edge((i + 1) * h + j, i * h + j, 1);
}
}
}
int flowcnt = mcf_graph.max_flow(st, go);
int bcnt = 0, wcnt = 0;
rep(i, h) rep(j, w) {
if (s[i][j] == 'w') wcnt++;
else if (s[i][j] == 'b')
bcnt++;
}
cout << 100 * flowcnt + (min(bcnt, wcnt) - flowcnt) * 10 + max(bcnt, wcnt) - min(bcnt, wcnt) << endl;
// cout << flowcnt << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0