QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#113158 | #1943. Borders | ckiseki# | WA | 3ms | 4856kb | C++14 | 4.1kb | 2023-06-16 15:54:34 | 2023-06-16 15:54:37 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int g[maxn][maxn];
int vis[maxn][maxn], cid[maxn][maxn];
void dfs(int i, int j) {
vis[i][j] = true;
for (int k = 0; k < 4; k++) {
if (g[i + dx[k]][j + dy[k]] != g[i][j]) continue;
if (vis[i + dx[k]][j + dy[k]]) continue;
cid[i + dx[k]][j + dy[k]] = cid[i][j];
dfs(i + dx[k], j + dy[k]);
}
}
int color[maxn * maxn];
vector<int> nei[maxn * maxn];
int isborder[maxn * maxn];
template <typename Cap = int64_t>
class Dinic {
private:
struct E {
int to, rev;
Cap cap;
};
int n, st, ed;
vector<vector<E>> G;
vector<int> lv, idx;
bool BFS() {
lv.assign(n, -1);
queue<int> bfs;
bfs.push(st);
lv[st] = 0;
while (not bfs.empty()) {
int u = bfs.front(); bfs.pop();
for (auto e: G[u]) {
if (e.cap <= 0 or lv[e.to] != -1)
continue;
bfs.push(e.to);
lv[e.to] = lv[u] + 1;
}
}
return lv[ed] != -1;
}
Cap DFS(int u, Cap f) {
if (u == ed) return f;
Cap ret = 0;
for (int &i = idx[u]; i < int(G[u].size()); ++i) {
auto &e = G[u][i];
if (e.cap <= 0 or lv[e.to] != lv[u] + 1) continue;
Cap nf = DFS(e.to, min(f, e.cap));
ret += nf; e.cap -= nf; f -= nf;
G[e.to][e.rev].cap += nf;
if (f == 0) return ret;
}
if (ret == 0) lv[u] = -1;
return ret;
}
public:
void init(int n_) { G.assign(n = n_, vector<E>()); }
void add_edge(int u, int v, Cap c) {
G[u].push_back({ v, int(G[v].size()), c });
G[v].push_back({ u, int(G[u].size())-1, 0 });
}
Cap max_flow(int st_, int ed_) {
st = st_, ed = ed_; Cap ret = 0;
while (BFS()) {
idx.assign(n, 0);
Cap f = DFS(st, numeric_limits<Cap>::max());
ret += f;
if (f == 0) break;
}
return ret;
}
};
Dinic<int> flow;
signed main() {
cin.tie(nullptr) -> sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < m; j++)
g[i + 1][j + 1] = s[j];
}
int c = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!vis[i][j])
cid[i][j] = ++c, color[c] = g[i][j], dfs(i, j);
}
}
for (int i = 1; i + 1 <= n; i++) {
for (int j = 1; j <= m; j++) {
if (cid[i][j] != cid[i + 1][j]) {
nei[cid[i][j]].emplace_back(cid[i + 1][j]);
nei[cid[i + 1][j]].emplace_back(cid[i][j]);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j + 1 <= m; j++) {
if (cid[i][j] != cid[i][j + 1]) {
nei[cid[i][j]].emplace_back(cid[i][j + 1]);
nei[cid[i][j + 1]].emplace_back(cid[i][j]);
}
}
}
for (int i = 1; i <= n; i++) {
isborder[cid[i][1]] = true;
isborder[cid[i][m]] = true;
}
for (int j = 1; j <= m; j++) {
isborder[cid[1][j]] = true;
isborder[cid[n][j]] = true;
}
flow.init(c + 2);
int S = 0, T = c + 1;
for (int i = 1; i <= c; i++) {
if (color[i] == '0') {
flow.add_edge(S, i, 1);
if (isborder[i]) {
flow.add_edge(i, T, 1e9);
}
} else {
flow.add_edge(i, T, 1);
if (isborder[i]) {
flow.add_edge(S, i, 1e9);
}
}
}
for (int a = 1; a <= n; a++) {
if (color[a] == '0') {
for (int b: nei[a]) {
flow.add_edge(a, b, 1e9);
}
}
}
int f = flow.max_flow(S, T);
cout << f << '\n';
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 4856kb
input:
100 100 0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101 1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010 010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...
output:
396
result:
wrong answer 1st lines differ - expected: '5198', found: '396'