QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#635525 | #9412. Stop the Castle | FangYifan | RE | 0ms | 0kb | C++17 | 6.9kb | 2024-10-12 20:03:42 | 2024-10-12 20:03:42 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
constexpr int mod = 998244353;
constexpr int N = 1e6 + 10;
template <class T>
struct Flow {
T inf;
int n;
struct Edge {
int v;
T cap;
Edge(int v, T cap) : v(v), cap(cap) {}
};
vector<Edge> e; // e[i] 存编号为 i 的边所指向的节点 v / 流量 cap
vector<vector<int>> g; // g[u] 存储了所有以 u 为起点的边 u -> v 的编号 i
vector<int> cur, deep;
Flow(int n) : inf(numeric_limits<T>::max()), n(n), g(n + 1) {}
bool bfs(int s, int t) {
deep.assign(n + 1, -1);
queue<int> q;
deep[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i : g[u]) {
auto [v, c] = e[i];
if (c > 0 && deep[v] == -1) {
deep[v] = deep[u] + 1;
if (v == t) return true;
q.push(v);
}
}
}
return false;
}
T dfs(int u, int t, T flow) {
if (u == t) return flow;
T remain = flow;
for (int &i = cur[u]; i < (int)g[u].size(); i++) {
int j = g[u][i];
auto [v, c] = e[j];
if (c > 0 && deep[v] == deep[u] + 1) {
T cost = dfs(v, t, min(remain, c));
e[j].cap -= cost;
e[j ^ 1].cap += cost;
remain -= cost;
if (remain == 0) return flow;
}
}
return flow - remain;
}
void add(int u, int v, T cap) {
g[u].push_back(e.size());
e.emplace_back(v, cap);
g[v].push_back(e.size());
e.emplace_back(u, 0);
}
// 最大流: 从源点 s 到汇点 t 的最大流量
T max_flow(int s, int t) {
T ans = 0;
while (bfs(s, t)) {
cur.assign(n + 1, 0);
ans += dfs(s, t, inf);
}
return ans;
}
// 最小割: 分割源点 s 到汇点 t 容量和最小的割边集合,最小割 = 最大流
vector<int> min_cut_ST() { // 标记最小割 (S, T)
vector<int> c(n + 1);
for (int i = 1; i <= n; i++) {
c[i] = (deep[i] != -1); // 源点 s 可到达节点 i
}
return c;
}
struct _Edge {
int u, v;
T cap;
T flow;
};
vector<_Edge> edges() {
vector<_Edge> t;
for (int i = 0; i < e.size(); i += 2) {
_Edge x;
x.u = e[i + 1].v;
x.v = e[i].v;
x.cap = e[i].cap + e[i + 1].cap;
x.flow = e[i + 1].cap;
t.push_back(x);
}
return t;
}
};
struct point { int x, y; };
void solve() {
int n, m;
vector<point> p(n + 1), obs(n + 1);
cin >> n; for (int i = 1; i <= n; i++) cin >> p[i].x >> p[i].y;
cin >> m; for (int i = 1; i <= m; i++) cin >> obs[i].x >> obs[i].y;
// 两车相邻,判断无解
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (p[i].x == p[j].x && abs(p[i].y - p[j].y) == 1) {
cout << "-1\n";
return;
} else if (p[i].y == p[j].y && abs(p[i].x - p[j].x) == 1) {
cout << "-1\n";
return;
}
}
}
// 每一行 / 每一列 维护坐标
map<int, vector<pair<int, int>>> r, c;
for (int i = 1; i <= n; i++) {
r[p[i].x].push_back({p[i].y, 1});
c[p[i].y].push_back({p[i].x, 1});
}
for (int i = 1; i <= m; i++) {
r[obs[i].x].push_back({obs[i].y, 2});
c[obs[i].y].push_back({obs[i].x, 2});
}
for (auto &[x, y] : r) sort(y.begin(), y.end());
for (auto &[x, y] : c) sort(y.begin(), y.end());
// 离散化坐标 -> 实际坐标
int numr = r.size(), numc = c.size();
vector<int> X(numr + 1), Y(numc + 1);
auto it = r.begin();
for (auto i = 1; i <= numr; i++, it++) X[i] = it->first;
it = c.begin();
for (auto i = 1; i <= numc; i++, it++) Y[i] = it->first;
// 对于行列碰撞的交点 (x, y),建立 x -> y 的有向边,容量为 1,那么求最大流即可
Flow<int> f(numr + numc + 2);
int S = numr + numc + 1, T = numr + numc + 2;
for (int i = 1; i <= numr; i++) f.add(S, i, 1);
for (int i = 1; i <= numc; i++) f.add(numr + i, T, 1);
map<pair<int, int>, array<pair<int, int>, 4>> insect;
for (int i = 1; i <= numr; i++) {
for (int j = 1; j <= numc; j++) {
int x = X[i], y = Y[j];
if (!r.count(x) || !c.count(y)) continue;
auto r2 = lower_bound(r[x].begin(), r[x].end(), make_pair(y, 0));
auto c2 = lower_bound(c[y].begin(), c[y].end(), make_pair(x, 0));
auto r1 = r2, c1 = c2;
if (r1 == r[x].begin() || c1 == c[y].begin()) continue;
r1--; c1--;
if (r1->first < y && r1->second == 1 && r2->first > y && r2->second == 1) {
if (c1->first < x && c1->second == 1 && c2->first > x && c2->second == 1) {
// cerr << "add: " << x << ' ' << y << "\n";
insect[{i, j}] = {make_pair(x, r1->first), make_pair(x, r2->first), make_pair(c1->first, y), make_pair(c2->first, y)};
f.add(i, numr + j, 1);
}
}
}
}
// 处理碰撞点对 and 对应的放置方案
set<pair<int, int>> st;
vector<pair<int, int>> ans;
f.max_flow(S, T);
auto e = f.edges();
for (auto [u, v, cap, flow] : e) {
if (u == S || v == T) continue;
if (flow == 1) {
v -= numr;
// cerr << "flow: " << X[u] << ' ' << Y[v] << "\n";
ans.emplace_back(X[u], Y[v]);
for (auto x : insect[{u, v}]) {
// cerr << "ban: " << x.first << ' ' << x.second << "\n";
st.insert(x);
}
}
}
for (auto [x, v] : r) {
for (int j = 1; j < v.size(); j++) {
if (v[j - 1].second == 1 && v[j].second == 1) {
int y1 = v[j - 1].first, y2 = v[j].first;
if (st.count({x, y1}) && st.count({x, y2})) continue;
ans.emplace_back(x, y1 + 1);
}
}
}
for (auto [y, v] : c) {
for (int j = 1; j < v.size(); j++) {
if (v[j - 1].second == 1 && v[j].second == 1) {
int x1 = v[j - 1].first, x2 = v[j].first;
if (st.count({x1, y}) && st.count({x2, y})) continue;
ans.emplace_back(x1 + 1, y);
}
}
}
cout << ans.size() << "\n";
for (auto [x, y] : ans) cout << x << ' ' << y << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
详细
Test #1:
score: 0
Runtime Error
input:
4 7 1 3 6 6 4 7 2 1 6 3 4 1 2 6 3 3 4 6 4 3 1 2 1 1 2 2 0 3 1 1 1 3 3 3 1 1 2 3 1 1 1 3 2 3 0