結果
問題 | No.421 しろくろチョコレート |
ユーザー | kimiyuki |
提出日時 | 2016-09-10 00:13:22 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,979 bytes |
コンパイル時間 | 658 ms |
コンパイル使用メモリ | 82,856 KB |
最終ジャッジ日時 | 2024-04-27 02:22:07 |
合計ジャッジ時間 | 1,434 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In function 'int maximum_flow_destructive(int, int, std::vector<std::vector<edge_t> >&)': main.cpp:39:24: error: 'numeric_limits' was not declared in this scope 39 | int f = dfs(s, numeric_limits<int>::max()); | ^~~~~~~~~~~~~~ main.cpp:39:39: error: expected primary-expression before 'int' 39 | int f = dfs(s, numeric_limits<int>::max()); | ^~~
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <array> #include <set> #include <map> #include <queue> #include <tuple> #include <unordered_set> #include <unordered_map> #include <functional> #include <cassert> #define repeat(i,n) for (int i = 0; (i) < (n); ++(i)) using namespace std; template <typename T, typename X> auto vectors(T a, X x) { return vector<T>(x, a); } template <typename T, typename X, typename Y, typename... Zs> auto vectors(T a, X x, Y y, Zs... zs) { auto cont = vectors(a, y, zs...); return vector<decltype(cont)>(x, cont); } struct edge_t { int to, cap, rev; }; int maximum_flow_destructive(int s, int t, vector<vector<edge_t> > & g) { // ford fulkerson, O(EF) int n = g.size(); vector<bool> used(n); function<int (int, int)> dfs = [&](int i, int f) { if (i == t) return f; used[i] = true; for (edge_t & e : g[i]) { if (used[e.to] or e.cap <= 0) continue; int nf = dfs(e.to, min(f, e.cap)); if (nf > 0) { e.cap -= nf; g[e.to][e.rev].cap += nf; return nf; } } return 0; }; int result = 0; while (true) { used.clear(); used.resize(n); int f = dfs(s, numeric_limits<int>::max()); if (f == 0) break; result += f; } return result; } void add_edge(vector<vector<edge_t> > & g, int from, int to, int cap) { g[from].push_back((edge_t) { to, cap, int(g[ to].size() ) }); g[ to].push_back((edge_t) { from, 0, int(g[from].size() - 1) }); } const int dy[4] = { -1, 1, 0, 0 }; const int dx[4] = { 0, 0, 1, -1 }; int main() { // input int h, w; cin >> h >> w; vector<vector<bool> > f = vectors(false, h, w); repeat (y,h) repeat (x,w) { char c; cin >> c; f[y][x] = c != '.'; } // compute auto is_on_field = [&](int y, int x) { return 0 <= y and y < h and 0 <= x and x < w; }; vector<vector<edge_t> > g(h * w + 2); auto index = [&](int y, int x) { return y * w + x; }; const int src = h * w; const int dst = h * w + 1; int white = 0, black = 0; repeat (y,h) repeat (x,w) { if (not f[y][x]) continue; if (y % 2 == x % 2) { white += 1; add_edge(g, src, index(y, x), 1); repeat (i,4) { int ny = y + dy[i]; int nx = x + dx[i]; if (not is_on_field(ny, nx)) continue; if (not f[ny][nx]) continue; add_edge(g, index(y, x), index(ny, nx), 1); } } else { black += 1; add_edge(g, index(y, x), dst, 1); } } int flow = maximum_flow_destructive(src, dst, g); int ans = 0; ans += flow * 100; white -= flow; black -= flow; int x = min(white, black); ans += x * 10; white -= x; black -= x; ans += max(white, black); // output cout << ans << endl; return 0; }