Untitled
unknown
plain_text
a year ago
6.1 kB
3
Indexable
#include <climits> #include <ios> #include <iostream> #include <queue> #include <vector> static constexpr int MAX_ROW = 110; static constexpr int MAX_COL = 110; static constexpr int MAX_NODES = MAX_ROW * MAX_COL; static constexpr int INF = INT_MAX; inline int to_in_id(int i, int j, int n, int m) { return i * m + j; } inline int to_out_id(int i, int j, int n, int m) { return i * m + j + n * m; } struct edge_type { int from; int to; long long capacity; long long flow{0}; int x{-1}; int y{-1}; int reverse_edge{-1}; bool reverse{true}; edge_type(int from, int to, long long capacity) : from(from), to(to), capacity(capacity) {} edge_type(int from, int to, long long capacity, int x, int y) : from(from), to(to), capacity(capacity), x(x), y(y), reverse(false) {} }; struct graph_type { int s; int t; std::vector<std::vector<edge_type>> edges; std::vector<int> distance; std::vector<int> path; std::queue<int> queue; graph_type(int s, int t) : s(s), t(t), edges(MAX_NODES, std::vector<edge_type>()), distance(MAX_NODES, -1), path(MAX_NODES, 0) {} void add_edge(int from, int to, long long capacity) { edges[from].emplace_back(from, to, capacity); edges[to].emplace_back(to, from, 0); edges[to].back().reverse_edge = edges[from].size() - 1; edges[from].back().reverse_edge = edges[to].size() - 1; } void add_edge(int from, int to, long long capacity, int x, int y) { edges[from].emplace_back(from, to, capacity, x, y); } bool bfs() { std::fill(distance.begin(), distance.end(), -1); distance[s] = 0; queue.push(s); while (!queue.empty()) { int v = queue.front(); queue.pop(); for (auto &to : edges[v]) { if (distance[to.to] == -1 && to.flow < to.capacity) { distance[to.to] = distance[v] + 1; queue.push(to.to); } } } return distance[t] != -1; } long long dfs(int v, long long min_flow) { if (v == t) { return min_flow; } for (size_t i = path[v]; i < edges[v].size(); ++i) { auto &to = edges[v][i]; if (to.flow < to.capacity && distance[to.to] == distance[v] + 1) { long long flow = dfs(to.to, std::min(min_flow, to.capacity - to.flow)); if (flow) { to.flow += flow; if (to.reverse_edge != -1) { edges[to.to][to.reverse_edge].flow -= flow; } return flow; } } path[v] = i + 1; } return 0; } long long max_flow() { long long flow = 0; while (bfs()) { std::fill(path.begin(), path.end(), 0); while (true) { long long pushed_flow = dfs(s, INF); flow += pushed_flow; if (!pushed_flow) { break; } } } return flow; } void dfs(int v, std::vector<bool> &visited, std::vector<int> &reached) { visited[v] = true; reached.push_back(v); for (const auto &edge : edges[v]) { if (!visited[edge.to]) { if (edge.flow < edge.capacity) { dfs(edge.to, visited, reached); } } } } int min_cut(std::vector<std::pair<int, int>> &coordinates) { std::vector<bool> visited(MAX_NODES, false); std::vector<int> reached; reached.reserve(MAX_NODES); dfs(s, visited, reached); int res = 0; for (int v : reached) { for (const auto &edge : edges[v]) { if (!visited[edge.to] && edge.flow == 1) { coordinates.emplace_back(edge.x, edge.y); ++res; break; } } } return res; } }; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int n, m; std::cin >> n >> m; std::vector<std::string> data(n, std::string(m, '-')); int t, k; std::cin >> k; std::cin >> t; int row, col; for (int i = 0; i < k; ++i) { std::cin >> row; std::cin >> col; data[row - 1][col - 1] = '#'; } for (int i = 0; i < t; ++i) { std::cin >> row; std::cin >> col; data[row - 1][col - 1] = '.'; } int source, sink; std::cin >> row; std::cin >> col; data[row - 1][col - 1] = 'A'; source = to_out_id(row - 1, col - 1, n, m); std::cin >> row; std::cin >> col; data[row - 1][col - 1] = 'B'; sink = to_in_id(row - 1, col - 1, n, m); graph_type graph(source, sink); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { switch (data[i][j]) { case '-': graph.add_edge(to_in_id(i, j, n, m), to_out_id(i, j, n, m), INF, i, j); break; case '.': graph.add_edge(to_in_id(i, j, n, m), to_out_id(i, j, n, m), 1, i, j); break; case '#': graph.add_edge(to_in_id(i, j, n, m), to_out_id(i, j, n, m), 0, i, j); break; } } } for (int i = 0; i < n - 1; ++i) { for (int j = 0; j < m - 1; ++j) { graph.add_edge(to_out_id(i, j, n, m), to_in_id(i + 1, j, n, m), INF); graph.add_edge(to_out_id(i + 1, j, n, m), to_in_id(i, j, n, m), INF); graph.add_edge(to_out_id(i, j, n, m), to_in_id(i, j + 1, n, m), INF); graph.add_edge(to_out_id(i, j + 1, n, m), to_in_id(i, j, n, m), INF); } } for (int i = 0; i < n - 1; ++i) { graph.add_edge(to_out_id(i, m - 1, n, m), to_in_id(i + 1, m - 1, n, m), INF); graph.add_edge(to_out_id(i + 1, m - 1, n, m), to_in_id(i, m - 1, n, m), INF); } for (int j = 0; j < m - 1; ++j) { graph.add_edge(to_out_id(n - 1, j, n, m), to_in_id(n - 1, j + 1, n, m), INF); graph.add_edge(to_out_id(n - 1, j + 1, n, m), to_in_id(n - 1, j, n, m), INF); } auto max_flow = graph.max_flow(); if (max_flow >= INF) { std::cout << "-1\n"; return 0; } std::vector<std::pair<int, int>> coordinates; coordinates.reserve(MAX_NODES); std::cout << graph.min_cut(coordinates) << "\n"; for (size_t i = 0; i < coordinates.size(); ++i) { std::cout << (coordinates[i].first + 1) << " " << (coordinates[i].second + 1) << "\n"; } return 0; }
Editor is loading...
Leave a Comment