Untitled
unknown
plain_text
a year ago
5.7 kB
4
Indexable
#include <cstdint> #include <ios> #include <iostream> #include <string> #include <vector> struct vertex_type { std::vector<int> neighbors; bool deleted{false}; vertex_type() { neighbors.reserve(4); } }; bool kuhn(int vertex, const std::vector<vertex_type> &graph, std::vector<int> &match, std::vector<bool> &visited) { if (visited[vertex] || graph[vertex].deleted) { return false; } visited[vertex] = true; for (size_t i = 0; i < graph[vertex].neighbors.size(); ++i) { int to = graph[vertex].neighbors[i]; if (graph[to].deleted) { continue; } if (match[to] == -1 || kuhn(match[to], graph, match, visited)) { match[to] = vertex; match[vertex] = to; return true; } } return false; } bool kuhn_check(int vertex, const std::vector<vertex_type> &graph, const std::vector<int> &match, std::vector<bool> &visited) { if (visited[vertex]) { return false; } visited[vertex] = true; for (size_t i = 0; i < graph[vertex].neighbors.size(); ++i) { int to = graph[vertex].neighbors[i]; if (graph[to].deleted) { continue; } if (match[to] == -1 || kuhn_check(match[to], graph, match, visited)) { return true; } } return false; } inline std::vector<int> calc_match(const std::vector<vertex_type> &graph) { std::vector<int> match(graph.size(), -1); std::vector<bool> visited_base(graph.size(), false); for (size_t i = 0; i < graph.size(); ++i) { if (graph[i].deleted) { visited_base[i] = true; continue; } for (size_t j = 0; j < graph[i].neighbors.size(); ++j) { int to = graph[i].neighbors[j]; if (graph[to].deleted) { continue; } if (match[to] == -1) { match[to] = i; visited_base[i] = true; break; } } } for (size_t i = 0; i < graph.size(); ++i) { if (visited_base[i]) { continue; } std::vector<bool> visited(graph.size(), false); kuhn(i, graph, match, visited); } return match; } inline int count_match(const std::vector<int>& match) { int max_match = 0; for (size_t i = 0; i < match.size(); ++i) { if (match[i] != -1) { ++max_match; } } return max_match; } void print_match(const std::vector<int>& match) { for (int i = 0; i < match.size(); ++i) { std::cout << match[i] << " "; } std::cout << "\n"; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int row, col; std::cin >> row; std::cin >> col; std::vector<vertex_type> graph; graph.reserve(row * col); std::vector<std::vector<int>> data(row, std::vector<int>(col, -1)); char ch; int vertex_count = 0; for (int r = 0; r < row; ++r) { for (int c = 0; c < col; ++c) { std::cin >> ch; if (ch == '.') { data[r][c] = vertex_count; ++vertex_count; } } } for (int r = 0; r < row; ++r) { for (int c = 0; c < col; ++c) { if (data[r][c] != -1) { graph.emplace_back(); auto &vertex = graph[data[r][c]]; if (r > 0 && data[r - 1][c] != -1) { vertex.neighbors.push_back(data[r - 1][c]); } if (r + 1 < row && data[r + 1][c] != -1) { vertex.neighbors.push_back(data[r + 1][c]); } if (c > 0 && data[r][c - 1] != -1) { vertex.neighbors.push_back(data[r][c - 1]); } if (c + 1 < col && data[r][c + 1] != -1) { vertex.neighbors.push_back(data[r][c + 1]); } } } } auto match = calc_match(graph); int max_match = count_match(match); //int max_match = count_match(match); // print_match(match); // std::cout << "\n"; for (int r = 0; r < row; ++r) { for (int c = 0; c < col; ++c) { if (data[r][c] == -1) { std::cout << "#"; continue; } //auto match_count = max_match; if (match[data[r][c]] != -1) { graph[data[r][c]].deleted = true; auto copy_match = match; int to = match[data[r][c]]; copy_match[data[r][c]] = -1; copy_match[to] = -1; std::vector<bool> visited(graph.size(), false); visited[data[r][c]] = true; for (size_t i = 0; i < graph.size(); ++i) { if (i == data[r][c] || copy_match[i] != -1) { continue; } kuhn(i, graph, copy_match, visited); } std::cout << (count_match(copy_match) == max_match ? 'L' : 'W'); // match[data[r][c]] = to; // match[to] = data[r][c]; // same = false; // //std::vector<bool> visited(graph.size(), false); // //kuhn(to, graph, copy_match, visited); // //print_match(copy_match); // { // std::vector<bool> visited(graph.size(), false); // if (kuhn(to, graph, copy_match, visited)) { // same = true; // } else { // for (int i = 0; !same && i < match.size(); ++i) { // if (copy_match[i] != -1) { // continue; // } // { // std::vector<bool> visited(graph.size(), false); // if (kuhn(i, graph, copy_match, visited)) { // same = true; // break; // } // } // } // } // } graph[data[r][c]].deleted = false; } else { std::cout << 'L'; } //std::cout << (match_count == max_match ? 'L' : 'W'); } std::cout << "\n"; } return 0; }
Editor is loading...
Leave a Comment