結果
| 問題 | No.421 しろくろチョコレート |
| ユーザー |
 ferin
|
| 提出日時 | 2019-10-25 15:03:29 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 3,825 bytes |
| コンパイル時間 | 2,166 ms |
| コンパイル使用メモリ | 185,232 KB |
| 実行使用メモリ | 40,832 KB |
| 最終ジャッジ日時 | 2024-07-19 19:01:19 |
| 合計ジャッジ時間 | 6,076 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | TLE | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
#ifdef DEBUG_
#include "../program_contest_library/memo/dump.hpp"
#else
#define dump(...)
#endif
const ll INF = 1LL<<60;
struct min_cost_max_flow {
struct edge {
int to;
ll cap, cost;
int rev;
bool isrev;
};
int n, s, t;
ll neg;
vector<vector<edge>> g;
vector<ll> d, h, dist, prevv, preve;
ll flow(vector<ll> d0) {
ll res = 0;
priority_queue<PII, vector<PII>, greater<PII>> que;
h.assign(n, 0);
preve.assign(n, -1);
prevv.assign(n, -1);
ll f = 0;
REP(i, d.size()) {
if(i < (ll)d0.size()) d[i] += d0[i];
if(d[i] > 0) add_edge(s, i, d[i], 0), f += d[i];
else add_edge(i, t, -d[i], 0);
}
while(f > 0) {
dist.assign(n, INF);
dist[s] = 0;
que.push({0, s});
while(que.size()) {
PII p = que.top(); que.pop();
int v = p.second;
if(dist[v] < p.first) continue;
REP(i, g[v].size()) {
edge &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;
que.push({dist[e.to], e.to});
}
}
}
if(dist[t] == INF) return -1;
REP(v, n) h[v] += dist[v];
ll d = f;
for(int v = t; v != s; v = prevv[v]) {
chmin(d, g[prevv[v]][preve[v]].cap);
}
f -= d; res += d * h[t];
for(int v = t; v != s; v = prevv[v]) {
edge &e = g[prevv[v]][preve[v]];
e.cap -= d;
g[v][e.rev].cap += d;
}
}
return neg + res;
}
min_cost_max_flow(int n0) : n(n0+2), s(n0), t(n0+1), neg(0), g(n0+2), d(n0+2) {}
void add_edge(int from, int to, ll cap, ll cost) {
if(cost >= 0) {
g[from].push_back({to, cap, cost, (int)g[to].size(), true});
g[to].push_back({from, 0, -cost, (int)g[from].size()-1, false});
} else {
d[from] -= cap;
d[to] += cap;
neg += cap * cost;
add_edge(to, from, cap, -cost);
}
}
// SからTに流量fを流す
// 流せないなら-1
ll flow(int S, int T, ll f) {
vector<ll> d0(n);
d0[S] = f, d0[T] = -f;
return flow(d0);
}
};
int main(void) {
ll h, w;
cin >> h >> w;
vector<string> a(h);
REP(i, h) cin >> a[i];
min_cost_max_flow graph(h*w+2);
ll s = h*w, t = s+1, f = 0;
REP(i, h) REP(j, w) {
if(a[i][j]=='w') {
graph.add_edge(s, i*w+j, 1, 0);
graph.add_edge(i*w+j, t, 1, -1);
f++;
} else {
graph.add_edge(s, i*w+j, 1, -1);
graph.add_edge(i*w+j, t, 1, 0);
}
if(a[i][j]!='w') continue;
REP(y, h) REP(x, w) {
if(a[y][x]!='b') continue;
if(abs(y-i)+abs(x-j) == 1) {
graph.add_edge(i*w+j, y*w+x, 1, -100);
} else {
graph.add_edge(i*w+j, y*w+x, 1, -10);
}
}
}
cout << -graph.flow(s, t, f) << endl;
return 0;
}