QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#798756 | #9665. Black-White Cubic Lattice | ucup-team004 | AC ✓ | 45ms | 4920kb | C++23 | 4.0kb | 2024-12-04 16:47:10 | 2024-12-04 16:47:10 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
template<class T>
struct MaxFlow {
struct _Edge {
int to;
T cap;
_Edge(int to, T cap) : to(to), cap(cap) {}
};
int n;
std::vector<_Edge> e;
std::vector<std::vector<int>> g;
std::vector<int> cur, h;
MaxFlow() {}
MaxFlow(int n) {
init(n);
}
void init(int n) {
this->n = n;
e.clear();
g.assign(n, {});
cur.resize(n);
h.resize(n);
}
bool bfs(int s, int t) {
h.assign(n, -1);
std::queue<int> que;
h[s] = 0;
que.push(s);
while (!que.empty()) {
const int u = que.front();
que.pop();
for (int i : g[u]) {
auto [v, c] = e[i];
if (c > 0 && h[v] == -1) {
h[v] = h[u] + 1;
if (v == t) {
return true;
}
que.push(v);
}
}
}
return false;
}
T dfs(int u, int t, T f) {
if (u == t) {
return f;
}
auto r = f;
for (int &i = cur[u]; i < int(g[u].size()); ++i) {
const int j = g[u][i];
auto [v, c] = e[j];
if (c > 0 && h[v] == h[u] + 1) {
auto a = dfs(v, t, std::min(r, c));
e[j].cap -= a;
e[j ^ 1].cap += a;
r -= a;
if (r == 0) {
return f;
}
}
}
return f - r;
}
void addEdge(int u, int v, T c) {
g[u].push_back(e.size());
e.emplace_back(v, c);
g[v].push_back(e.size());
e.emplace_back(u, 0);
}
T flow(int s, int t) {
T ans = 0;
while (bfs(s, t)) {
cur.assign(n, 0);
ans += dfs(s, t, std::numeric_limits<T>::max());
}
return ans;
}
std::vector<bool> minCut() {
std::vector<bool> c(n);
for (int i = 0; i < n; i++) {
c[i] = (h[i] != -1);
}
return c;
}
struct Edge {
int from;
int to;
T cap;
T flow;
};
std::vector<Edge> edges() {
std::vector<Edge> a;
for (int i = 0; i < e.size(); i += 2) {
Edge x;
x.from = e[i + 1].to;
x.to = e[i].to;
x.cap = e[i].cap + e[i + 1].cap;
x.flow = e[i + 1].cap;
a.push_back(x);
}
return a;
}
};
constexpr int inf = 1E9;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, M, L;
std::cin >> N >> M >> L;
std::vector s(L, std::vector<std::string>(N));
std::vector c(L, std::vector(N, std::vector<int>(M)));
for (int i = 0; i < L; i++) {
for (int j = 0; j < N; j++) {
std::cin >> s[i][j];
}
}
MaxFlow<int> g(N * M * L + 2);
const int S = N * M * L, T = S + 1;
for (int i = 0; i < L; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < M; k++) {
std::cin >> c[i][j][k];
if (s[i][j][k] == 'W') {
g.addEdge((i * N + j) * M + k, T, c[i][j][k]);
} else {
g.addEdge(S, (i * N + j) * M + k, c[i][j][k]);
}
if (i > 0) {
g.addEdge((i * N + j) * M + k, ((i - 1) * N + j) * M + k, inf);
}
if (j > 0) {
g.addEdge((i * N + j) * M + k, (i * N + (j - 1)) * M + k, inf);
}
if (k > 0) {
g.addEdge((i * N + j) * M + k, (i * N + j) * M + (k - 1), inf);
}
}
}
}
g.addEdge(S, 0, inf);
g.addEdge(N * M * L - 1, T, inf);
int ans = g.flow(S, T);
std::cout << ans << "\n";
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3588kb
input:
2 2 2 WW WW BB BB 1 1 1 1 2 2 2 2
output:
5
result:
ok single line: '5'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
2 1 1 W B 0 1
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 15ms
memory: 4920kb
input:
1 1 5000 B W W W W W W W W B B B W B W B W B W W B W W B B W B B B B W W W W W W W B B B B B B B B B W B B W B B B W W B B W W W W W W W B B B B W B B W B W W W W W B B W B B W W B W B B B B W W W B B W B W W W W W B W B B B W W B W B B W B W B B B B B W B B W W W W B W B W B W B W B B W B B B W W W...
output:
1218
result:
ok single line: '1218'
Test #4:
score: 0
Accepted
time: 16ms
memory: 4672kb
input:
5000 1 1 B W B W B B B B W W W W B W W W W W W W B B B B B B W W W B B B B B B B W B W B W B B W B B W B B B W B W B B B B W B W W B W B W B W W W W B B W W W B W W W W B W B W B W W W W B B W B W B W B B W W W B B B B W W W B W B W B B B W B W B W B B B W B W B B B W B B B B W W B W B W W W W W B W...
output:
242900000
result:
ok single line: '242900000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 4056kb
input:
1 5000 1 WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW...
output:
100000
result:
ok single line: '100000'
Test #6:
score: 0
Accepted
time: 42ms
memory: 4088kb
input:
2 2500 1 BWBBWWWBBBWBWBBBBBBBWBBBBBWWWWBBWBWWBBBBBBBBBWBWBWBBWWBBWWWBBWWWBBWWWWBWBBBWWBWBWBWWBBBWBWWWWWWWWWBBBBWWWBBBBWWBWBWBWBWBWWBWBBBBBBWBBWWWBWWBWWBWWBWWWBWWWBBBBBBBWBBWWBWWWWWWWBBBBWWBBBBBWWWBBBBBBWBWWWBWWWWBBBBWWWWWBWWBBBBWWWBWWBBWBWBBWWWBBBWWBBWBBWWBWWBBWBWBBWBWWWBWWWWWBBWWWBWWWWWWBWWWBBBWWBW...
output:
12335546
result:
ok single line: '12335546'
Test #7:
score: 0
Accepted
time: 39ms
memory: 4256kb
input:
1666 3 1 WBB WWB BWB BWW WWB WWB BBB BBB BBW WBB BBB BBW BWW WWB BBB BBW WWW BBW WWW BWW BWB WWB BWB WWW BWB BWW WWB BWW BWB BBB BBW BBB BWB WWB WBW WWB BWB BWW BWB WWW BBW BBW BBW BWW BWB BBB WWB BBB BBB WBB BBW BBB BBW BBB BBB WBW BBW WBW BBB BWB WBW BBW WWW WWW WWW BWB WWB BBW WBB WWB BWW BBW WBW...
output:
11971988
result:
ok single line: '11971988'
Test #8:
score: 0
Accepted
time: 45ms
memory: 4628kb
input:
4 1 1250 W B W B B W B B B W B B W W W W B B B B W B B B B W W B W W B W W B W W B B W B B W B B W B W W B W W B W B W B W W W B B B W W B B W B B B W B B W W W B B W B W B B B W B B W B W B B B B B W W W B W B W W W W B W B W B B B W W B W W W W W B B B B B W W W W B B W W W W W B B B B B B W W W B...
output:
12131611
result:
ok single line: '12131611'
Test #9:
score: 0
Accepted
time: 8ms
memory: 4112kb
input:
70 71 1 WBBWBBBWWBBBWWWBBBWWBWWWBWBBBWBWWWWWBWWBBWBWWWBWBWWBBWWBBWWBBBWBWWWWWWB WWBBBWWBWWBWBBWBBWWWWBBBWWWBBWWBBWWWWWBWWWBWWBWWBWBWWBBWWBBWBWWBWBWBBWW BWWWBWBBBBWWWWWWBWWBBWWBWWWWWBWWWWBBWBBWBWBWWBWWBBBBWBBBBWBBWWWWBBBBWWB BWBWBWBBWWWBBWWBBWWBWWBBWWBWBBWBWBBWBWWBWWBBBWBWWWBBWBBBWWWBBWBBBWWWBBW WWWW...
output:
11904642
result:
ok single line: '11904642'
Test #10:
score: 0
Accepted
time: 17ms
memory: 4380kb
input:
12 4 95 BBWW WBWW BWBW WWBW BWBB BWBW WBWW BWWB WWBW BWBW WWWB BWBW WWWB WBWB BWBB BBBW WBBB BWWW BWWW BBWW WWBW WBWB WWBB WWWW WBWW BBBW WBBB WWWW WBBW BBBB WWBB WBWW WWWW BBWW WBBW WWBW WWWB WWWB BWWW BWWW BWWB BWBW BBBB WWWB WBBB WWWB WWWW WBWB WWWB BBBB WWBB WBBW BBWB BBWB WWWW WWBW WBWW WBWW WW...
output:
10402
result:
ok single line: '10402'
Test #11:
score: 0
Accepted
time: 8ms
memory: 4376kb
input:
25 10 20 BBWBWBWBBW BBBWBBWBWW WBWBWBWWWB WBWBBWBWBW WWWWWWWBWB BBWBWBWWBB BBBBBWBWWB BWWWWBWWBW BWBBBBWWWW WWBBWBWBWW WWBWWWBBWW BWBWWBBWBB BBWBBWBWWB WBBBBBWWWW BBWWBBBWWB WWWWBWWWWB WBBBWWBWBW WBBWBWWBBB BBWBWWBBWW WWBWBWBWWB BBBBWWBWBB WWWWWWBBWB WWWBWWBBBW WBBWWWWBWW BBBWWWBWWB BWWWBWBBBB BBBWW...
output:
11106
result:
ok single line: '11106'
Test #12:
score: 0
Accepted
time: 11ms
memory: 4404kb
input:
50 2 50 BB WB BB BB BB BW BW WW BB WB WW BW WB BB BW WW BW BW BB WB WB BW WB WB WW WW WB BB WW BW WB BW WW BB BW BB BW BB WB WW WW WW BB WW BW BB BB BB BB WB BW WW WB BW BW BW WW WB BB WW WW BB WW BB WB BB BW BB BB WB WW BB WW WB WB WW WW BB BW WB WB WW WB WB WB WB BB WB WW BW WW BB WB BW BW WB WB W...
output:
11686
result:
ok single line: '11686'
Test #13:
score: 0
Accepted
time: 33ms
memory: 4076kb
input:
4 5 210 BWBWW BBBWW WBWWW WBWWW WBWBB BWBWW BBBWB WBBWB BWWWB BWBBB BWBBB WBBBB BBBBB WWBWB WBBBW WBWWB WBBBB BBWBB BWWBB WBBWW WWWBW WBBBW WWBBB WWBBB WWBWB BWBWW BWBBB BWWBB BBWBB BWWWB WWBBW WBBBB WBWBW BBWBW WBBBB BWBWW BBBWW BBWWW WWBBB WWWWB WWWBB BBBWB WWBWB BBWBW BBBBB BBBBB WWWWW BBWBB WWBW...
output:
9895
result:
ok single line: '9895'
Test #14:
score: 0
Accepted
time: 11ms
memory: 4168kb
input:
15 43 7 BWWWWBWBWBBBWWWWWBWBWBBBBBWWBBBBWWBWBWWBWBW BBWBWBWBBBWBBWWWWBWWWWWWBBBBBWWBWBWWWBBBWWB BWBBWBBBBBWBBWBBBWBBBBBBBWBBBBBWWWWBBBBBBBW BWBWWBBWBWBBBBWBBWBWWWWWWWBBWBWWBWBBWBBWBBB BBWWWBWWWBWWBWWBBWWWWWWWWBBWWWWWWBWBBBWWWBB WBWWBWBWBWWBWWWWWWWWBWWWBWWWWWBWWBBWBBBBWBW BBBBWWWBBWBBBBBBWWWBWBWWBBWW...
output:
10218
result:
ok single line: '10218'
Test #15:
score: 0
Accepted
time: 18ms
memory: 4384kb
input:
10 10 50 BBBBWWBBWW BWBBWBWWBB WWBBWWWWBB WBWWBBWWBW WBWBWBWBWW BBWBWWBWBB BWBWBBWBBB WWWBWBBBBW WBWWBBWWBW BWWWWBBWBB WWWWBWWWBW BBWBWWWBWB WWWWWWWBBB WBBBWWWWBB WWWBWBBBBW BWWWBWWWBB WWBBBBBBWB BWBBWBWWWB BBWWWWWWWB WWBWWBBWWW BWWWBWWBBB WWBBWWWBBB WWWBWWBWWW BWBWWBBWBW BBBBBWBWBW WBWWWWWBBB BBBBB...
output:
113532736
result:
ok single line: '113532736'
Test #16:
score: 0
Accepted
time: 10ms
memory: 4384kb
input:
16 17 18 WBWBWBWBWWWWBBWBB BBWBBWWWWBWBWBBBW BBWBWBBBBBWBWWBWB WBBBBBWWBBBBBWWBB WBBWWWWBWBWBWWWBW WBBWWWWWWBWWBWWBW WWBBBBBBBWWBBWBWB WWBWBWWWBWWWWBWBW BBBBBBBBBBWWWBBBW WWBBWBWBBWBBWBWWW WBBWBBBBBBWWWWWBW BBBBWWBBWBBBBBBBB WBWWBWWWBBWWWBWBW WBBWBBBBWBWBWBBWB WBBBWBWBWBBBWWWWB WWBWBWWWWBWWBWBWB WWB...
output:
109472675
result:
ok single line: '109472675'
Test #17:
score: 0
Accepted
time: 2ms
memory: 4116kb
input:
17 17 17 BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBB BBB...
output:
100000
result:
ok single line: '100000'
Test #18:
score: 0
Accepted
time: 6ms
memory: 4344kb
input:
17 17 17 WWWBBBBWWBBBWWBWW WWWWBBBBBWBBBBBWW BWWWBBWWBWBWBWWWW WBBBBWBWWBWBWWWWB BWWBWWWWWBWBBBBWW WBBBWWBBBBWBBBWWB BWWWBBBBWWBWBWBWW WWBWBWBBBBWBWBBBW WWBWWWBWBBWBWWWBW BWWBBWWBBBWBWBWWB BBBWBBBWWBWBWBWWB WWWBWWWBBWBBWWWBB WBBBWBWBBBWWWBBBW WBWBWBBBWBWBBWWWW BBBWWBWWBWWBWBBBB WBBBWBBWBBWBBBWBB WWW...
output:
1128
result:
ok single line: '1128'
Test #19:
score: 0
Accepted
time: 7ms
memory: 4096kb
input:
17 17 17 WWWBBWWBBWBWWBWWB BWWBBBWWWWWWWBWBB WWWBWBBBBBWWWWWBB WWWWWWBWBBBBWWWBW WBWWBBWWWBBWBWWWB BWBBWWWBBWWWBBBBW WBBBBWBWWWBWWWBBB WWWWWWWWBBWWWWWBW WWWWBBWBWWWWWBWWB BBBBBBWWBBBWBBBWW BBBBBBBBBWWWWWWWB BBWWWWBBWWBBWWBBB WBWBBBBWWBWBBWWBB BBBBWBWWWBBBBBBWB BWBWWWBBWWBBWBWBB BBWWWBWWBWBWWBWBB WBB...
output:
5346
result:
ok single line: '5346'
Test #20:
score: 0
Accepted
time: 13ms
memory: 4136kb
input:
17 17 17 WWBBWWWWWBWWWBBBW BWWWWWWBWBWWBBWWW WWWWWBWBWBWWWWWBW WWWWBWBBBBWBWWWWW BBBBWBBWWWWWBWWWW WBWWBWWWBBBBBWBBW BBWWWWWBWBBBBWBBW BWWBBBWBWWWBBWWBW WWBBWWWBBWWBBWBWB WBBBWBWBBBBBBBBWW BWWBWBBWBWWBWBBBB WWWBWWWWWBWBBWWWW BBBBBBWBWWWBWBBBB WWWWWBBBBBBWWWWWB BWBBWWWBWBBWWBBWB WBWBBBBBWBWBWWBBB WWW...
output:
113499454
result:
ok single line: '113499454'
Extra Test:
score: 0
Extra Test Passed