結果
| 問題 |
No.459 C-VS for yukicoder
|
| コンテスト | |
| ユーザー |
 hashiryo
|
| 提出日時 | 2021-12-16 14:46:04 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 66 ms / 2,000 ms |
| コード長 | 6,494 bytes |
| コンパイル時間 | 3,560 ms |
| コンパイル使用メモリ | 212,480 KB |
| 最終ジャッジ日時 | 2025-01-26 23:34:37 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 58 |
ソースコード
#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
// using namespace atcoder;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
os << "(" << p.first << "," << p.second << ")";
return os;
}
#ifdef __LOCAL
#define debug(x) cerr << __LINE__ << ": " << #x << " = " << (x) << '\n'
#define debugArray(x, n) \
cerr << __LINE__ << ": " << #x << " = {"; \
for (long long hoge = 0; (hoge) < (long long)(n); ++(hoge)) \
cerr << ((hoge) ? "," : "") << x[hoge]; \
cerr << "}" << '\n'
#define debugMatrix(x, h, w) \
cerr << __LINE__ << ": " << #x << " =\n"; \
for (long long hoge = 0; (hoge) < (long long)(h); ++(hoge)) { \
cerr << ((hoge ? " {" : "{{")); \
for (long long fuga = 0; (fuga) < (long long)(w); ++(fuga)) \
cerr << ((fuga ? ", " : "")) << x[hoge][fuga]; \
cerr << "}" << (hoge + 1 == (long long)(h) ? "}" : ",") << '\n'; \
}
#else
#define debug(x) (void(0))
#define debugArray(x, n) (void(0))
#define debugMatrix(x, h, w) (void(0))
#endif
template <typename FlowAlgo>
class MaxFlowLowerBound : public FlowAlgo {
using Edge = typename FlowAlgo::Edge;
using flow_t = decltype(Edge::cap);
std::vector<flow_t> in;
int add_edge(int src, int dst, flow_t cap) {
int e = this->adj[src].size();
int re = src == dst ? e + 1 : this->adj[dst].size();
this->adj[src].push_back(Edge{dst, re, cap});
this->adj[dst].push_back(Edge{src, e, 0});
return this->m++, re;
}
public:
MaxFlowLowerBound(std::size_t n = 0) : FlowAlgo(n + 2), in(n) {}
int add_vertex() {
return this->adj.resize(++this->n), in.resize(this->n - 2, 0), this->n - 3;
}
std::vector<int> add_vertices(const std::size_t size) {
std::vector<int> ret(size);
std::iota(ret.begin(), ret.end(), this->n - 2);
return this->adj.resize(this->n += size), in.resize(this->n - 2, 0), ret;
}
struct EdgePtr {
friend class MaxFlowLowerBound;
MaxFlowLowerBound *instance;
int v, e;
flow_t u;
Edge &edge() { return instance->adj[v][e]; }
Edge &rev() {
Edge &e = edge();
return instance->adj[e.dst][e.rev];
}
EdgePtr(MaxFlowLowerBound *instance, int v, int e, flow_t u)
: instance(instance), v(v), e(e), u(u) {}
public:
EdgePtr() = default;
int src() { return v; }
int dst() { return edge().dst; }
flow_t flow() { return u - edge().cap; }
flow_t lower() { return flow() - rev().cap; }
flow_t upper() { return u; }
};
EdgePtr add_edge(int src, int dst, flow_t lower, flow_t upper) {
assert(lower <= upper);
src += 2, dst += 2;
assert(0 <= src && src < this->n);
assert(0 <= dst && dst < this->n);
this->m++;
int e = this->adj[src].size();
int re = src == dst ? e + 1 : this->adj[dst].size();
if (lower * upper <= 0) {
this->adj[src].push_back(Edge{dst, re, upper});
this->adj[dst].push_back(Edge{src, e, -lower});
} else if (lower > 0) {
in[src - 2] -= lower, in[dst - 2] += lower;
this->adj[src].push_back(Edge{dst, re, upper - lower});
this->adj[dst].push_back(Edge{src, e, 0});
} else {
in[src - 2] -= upper, in[dst - 2] += upper;
this->adj[src].push_back(Edge{dst, re, 0});
this->adj[dst].push_back(Edge{src, e, upper - lower});
}
return EdgePtr(this, src, e, upper);
}
flow_t maxflow(int s, int t) {
static constexpr flow_t INF = std::numeric_limits<flow_t>::max();
flow_t sum = 0;
for (int i = this->n - 2; i--;) {
if (in[i] > 0) add_edge(0, i + 2, in[i]), sum += in[i];
if (in[i] < 0) add_edge(i + 2, 1, -in[i]);
}
int re = add_edge(t += 2, s += 2, INF);
if (this->flow(0, 1, INF) < sum) return -1; // no solution
return this->flow(s, t, INF) + this->adj[s][re].cap;
}
};
template <class flow_t>
struct Dinic {
Dinic(std::size_t _n = 0) : n(_n), m(0), adj(n) {}
protected:
struct Edge {
int dst, rev;
flow_t cap;
};
int n, m;
std::vector<std::vector<Edge>> adj;
std::vector<int> level, iter;
inline void levelize(const int &s, const int &t) {
level.assign(n, -1), level[s] = 0;
std::queue<int> que;
for (que.push(s); !que.empty();) {
int u = que.front();
que.pop();
for (auto &e : adj[u])
if (e.cap > 0 && level[e.dst] < 0) {
level[e.dst] = level[u] + 1;
if (e.dst == t) return;
que.push(e.dst);
}
}
}
inline flow_t dfs(int u, const int &s, flow_t cur) {
if (u == s) return cur;
flow_t ret = 0;
for (int &i = iter[u]; i < adj[u].size(); i++) {
Edge &e = adj[u][i], &re = adj[e.dst][e.rev];
if (level[u] <= level[e.dst] || re.cap == 0) continue;
flow_t f = dfs(e.dst, s, std::min(cur - ret, re.cap));
if (f <= 0) continue;
e.cap += f, re.cap -= f, ret += f;
if (ret == cur) return ret;
}
return level[u] = n, ret;
}
flow_t flow(int s, int t, flow_t flow_lim) {
assert(0 <= s && s < n);
assert(0 <= t && t < n);
assert(s != t);
flow_t ret = 0;
for (flow_t f; ret < flow_lim; ret += f) {
if (levelize(s, t), level[t] == -1) break;
iter.assign(n, 0);
if (!(f = dfs(t, s, flow_lim - ret))) break;
}
return ret;
}
};
signed main() {
cin.tie(0);
ios::sync_with_stdio(false);
cin.tie(0);
ios::sync_with_stdio(false);
int H, W, N;
cin >> H >> W >> N;
int height[W] = {0};
for (int i = 0; i < H; i++) {
string S;
cin >> S;
for (int j = 0; j < W; j++) height[j] += S[j] == '#';
}
using MF = MaxFlowLowerBound<Dinic<long long>>;
MF graph;
MF::EdgePtr e[N][3];
int s = graph.add_vertex(), t = graph.add_vertex();
auto p = graph.add_vertices(N), q = graph.add_vertices(W);
for (int i = 0; i < N; i++) {
int C;
cin >> C;
graph.add_edge(s, p[i], 1, 9);
for (int j = 0; j < 3; j++) e[i][j] = graph.add_edge(p[i], q[C + j], 0, 3);
}
for (int i = 0; i < W; i++) graph.add_edge(q[i], t, height[i], height[i]);
graph.maxflow(s, t);
for (int i = 0; i < N; i++) {
string ans[3] = {"...", "...", "..."};
for (int j = 0; j < 3; j++) {
auto f = e[i][j].flow();
for (int k = 0; k < f; k++) ans[k][j] = '#';
}
for (int j = 0; j < 3; j++) cout << ans[j] << '\n';
}
return 0;
return 0;
}