QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#440160 | #7178. Bishops | 0x3b800001 | WA | 1ms | 5604kb | C++14 | 2.6kb | 2024-06-13 10:49:04 | 2024-06-13 10:49:05 |
Judging History
answer
#include <iostream>
#include <queue>
namespace MF {
int n, s, t;
struct Edge {
int u, v, c, nxt;
} edges[20000007];
int ecnt;
int head[1000007];
void _addedge(int u, int v, int c) {
edges[ecnt].u = u, edges[ecnt].v = v, edges[ecnt].c = c;
edges[ecnt].nxt = head[u], head[u] = ecnt, ++ecnt;
}
void addedge(int u, int v, int c) { _addedge(u, v, c), _addedge(v, u, 0); }
int dis[1000007];
int cur[1000007];
bool BFS() {
for (int i = 1; i <= n; ++i) {
dis[i] = +0x3b9aca00;
cur[i] = head[i];
}
std::queue<int> q;
dis[s] = 0, q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int e = head[u]; e != -1; e = edges[e].nxt) {
if (edges[e].c != 0 && dis[u] + 1 < dis[edges[e].v]) {
dis[edges[e].v] = dis[u] + 1, q.push(edges[e].v);
}
}
}
return dis[t] != +0x3b9aca00;
}
int sF;
int dfs(int u, int fl) {
if (u == t) {
sF += fl;
return fl;
}
int rf = fl;
for (int& e = cur[u]; e != -1; e = edges[e].nxt) {
if (edges[e].c != 0 && dis[edges[e].v] == dis[u] + 1) {
int f = dfs(edges[e].v, std::min(fl, edges[e].c));
fl -= f, edges[e].c -= f, edges[e ^ 1].c += f;
if (fl == 0) {
return rf;
}
}
}
return rf - fl;
}
void init(int _n, int _s, int _t) {
n = _n, s = _s, t = _t;
for (int i = 1; i <= n; ++i) {
head[i] = -1;
}
}
int Dinic() {
while (BFS()) {
dfs(s, +0x3b9aca00);
}
return sF;
}
};
int n, m;
int main() {
// std::freopen("bishop.in", "r", stdin);
// std::freopen("bishop.out", "w", stdout);
std::cin.tie(nullptr)->sync_with_stdio(false);
std::cin >> n >> m;
MF::init(n + n + m + m, 1, n + n + m + m);
for (int i = 2; i <= n + m; ++i) {
MF::addedge(1, i, 1);
MF::addedge(i + n + m - 1, n + n + m + m, 1);
}
for (int i : std::vector<int>{1, 2, n - 1, n}) {
if (1 <= i && i <= n) {
for (int j = 1; j <= m; ++j) {
MF::addedge(i + j, i - j + n + m + m, 1);
}
}
}
for (int j : std::vector<int>{1, 2, m - 1, m}) {
if (1 <= j && j <= m) {
for (int i = 3; i <= n - 2; ++i) {
MF::addedge(i + j, i - j + n + m + m, 1);
}
}
}
std::cout << MF::Dinic() << '\n';
for (int i = 0; i < MF::ecnt; ++i) {
if (MF::edges[i].c == 0 && 2 <= MF::edges[i].u && MF::edges[i].u <= n + m && n + m + 1 <= MF::edges[i].v && MF::edges[i].v <= n + n + m + m - 1) {
int P = MF::edges[i].u, M = MF::edges[i].v - n - m - m;
// std::cout << (P + M) / 2 << ' ' << (P - M) / 2 << '\n';
}
}
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5604kb
input:
2 5
output:
6
result:
wrong output format Unexpected end of file - int32 expected