#include <algorithm> #include <functional> #include <iostream> #include <vector> int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); int n, m, k; std::cin >> n >> m >> k; if (k == n) { std::cout << '0'; return 0; } std::vector<std::vector<int>> graph(n); for (int i = 0; i < m; i++) { int x, y; std::cin >> x >> y; graph[x - 1].push_back(y - 1); } std::vector<int> longest_paths(n); std::vector<int> sources(n); std::function<int(int, std::vector<bool>&, std::vector<bool>)> f = [&](int left_to_remove, std::vector<bool>& removed, std::vector<bool> attempted) { int winner_index = 0; std::fill(longest_paths.begin(), longest_paths.end(), 1); std::fill(sources.begin(), sources.end(), -1); for (int i = 0; i < n; i++) { if (!removed[i]) { int longest = longest_paths[i]; if (longest > longest_paths[winner_index]) winner_index = i; for (const auto& edge : graph[i]) { int& edge_longest = longest_paths[edge]; if (edge_longest <= longest) { edge_longest = longest + 1; sources[edge] = i; } } } } int path_length = longest_paths[winner_index]; if (left_to_remove == 0) return path_length; left_to_remove--; std::vector<int> path(path_length); for (auto&& index : path) { index = winner_index; winner_index = sources[winner_index]; } int path_middle = path_length / 2; int best_result = path_length; for (int i = 1; i <= best_result; i++) { int index = path_middle + (i & 1 ? i : -i) / 2; int min_new_max_length = std::max(index, path_length - 1 - index); if (min_new_max_length / (k + 1) >= best_result) return best_result; int attempt = path[index]; if (!attempted[attempt]) { attempted[attempt] = true; removed[attempt] = true; int result = f(left_to_remove, removed, attempted); removed[attempt] = false; if (result < best_result) best_result = result; } } return best_result; }; std::vector<bool> removed(n); std::vector<bool> attempted(n); std::cout << f(k, removed, attempted); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | #include <algorithm> #include <functional> #include <iostream> #include <vector> int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); int n, m, k; std::cin >> n >> m >> k; if (k == n) { std::cout << '0'; return 0; } std::vector<std::vector<int>> graph(n); for (int i = 0; i < m; i++) { int x, y; std::cin >> x >> y; graph[x - 1].push_back(y - 1); } std::vector<int> longest_paths(n); std::vector<int> sources(n); std::function<int(int, std::vector<bool>&, std::vector<bool>)> f = [&](int left_to_remove, std::vector<bool>& removed, std::vector<bool> attempted) { int winner_index = 0; std::fill(longest_paths.begin(), longest_paths.end(), 1); std::fill(sources.begin(), sources.end(), -1); for (int i = 0; i < n; i++) { if (!removed[i]) { int longest = longest_paths[i]; if (longest > longest_paths[winner_index]) winner_index = i; for (const auto& edge : graph[i]) { int& edge_longest = longest_paths[edge]; if (edge_longest <= longest) { edge_longest = longest + 1; sources[edge] = i; } } } } int path_length = longest_paths[winner_index]; if (left_to_remove == 0) return path_length; left_to_remove--; std::vector<int> path(path_length); for (auto&& index : path) { index = winner_index; winner_index = sources[winner_index]; } int path_middle = path_length / 2; int best_result = path_length; for (int i = 1; i <= best_result; i++) { int index = path_middle + (i & 1 ? i : -i) / 2; int min_new_max_length = std::max(index, path_length - 1 - index); if (min_new_max_length / (k + 1) >= best_result) return best_result; int attempt = path[index]; if (!attempted[attempt]) { attempted[attempt] = true; removed[attempt] = true; int result = f(left_to_remove, removed, attempted); removed[attempt] = false; if (result < best_result) best_result = result; } } return best_result; }; std::vector<bool> removed(n); std::vector<bool> attempted(n); std::cout << f(k, removed, attempted); return 0; } |