#include <algorithm> #include <cstdio> #include <vector> struct MaxCompData { MaxCompData() {} MaxCompData(int complexity_, int prev_) : complexity(complexity_), prev(prev_) {} int complexity; int prev; }; const int MAX_N = 309; int n; std::vector<int> in[MAX_N]; std::vector<int> out[MAX_N]; bool is_removed[MAX_N]; void calc_max_complexity_ending_at(const int v, int* max_complexity) { if(is_removed[v]) return; if(max_complexity[v] != -1) return; max_complexity[v] = 1; for(const auto& u : in[v]) { if(is_removed[u]) continue; if(max_complexity[u] == -1) calc_max_complexity_ending_at(u, max_complexity); max_complexity[v] = std::max(max_complexity[v], max_complexity[u] + 1); } } int calc_max_complexity() { int max_complexity[MAX_N]; std::fill(max_complexity, max_complexity + n, -1); for(int i = n-1; i >= 0; --i) { if(!is_removed[i] && max_complexity[i] == -1) calc_max_complexity_ending_at(i, max_complexity); } return std::max(*std::max_element(max_complexity, max_complexity + n), 0); } void find_path_with_max_complexity_ending_at(const int v, MaxCompData* max_complexity) { if(is_removed[v]) return; if(max_complexity[v].complexity != -1) return; max_complexity[v].complexity = 1; for(const auto& u : in[v]) { if(is_removed[u]) continue; if(max_complexity[u].complexity == -1) find_path_with_max_complexity_ending_at(u, max_complexity); if(max_complexity[v].complexity < (max_complexity[u].complexity + 1)) { max_complexity[v].complexity = max_complexity[u].complexity + 1; max_complexity[v].prev = u; } } } std::vector<int> find_path_with_max_complexity() { MaxCompData max_complexity[MAX_N]; std::fill(max_complexity, max_complexity + n, MaxCompData(-1, -1)); for(int i = n-1; i >= 0; --i) { if(!is_removed[i] && max_complexity[i].complexity == -1) find_path_with_max_complexity_ending_at(i, max_complexity); } std::vector<int> result; int result_node = -1; int max_comp = -1; for(int i = 0; i < n; ++i) { if(max_complexity[i].complexity > max_comp) { max_comp = max_complexity[i].complexity; result_node = i; } } while(result_node != -1) { result.push_back(result_node); result_node = max_complexity[result_node].prev; } return result; } int find_max_complexity(const int k) { if(k == 0) return calc_max_complexity(); int result = 1000000; const auto to_remove = find_path_with_max_complexity(); for(const auto& v : to_remove) { is_removed[v] = true; result = std::min(result, find_max_complexity(k-1)); is_removed[v] = false; } return result; } int main() { int m, k; scanf("%d%d%d", &n, &m, &k); while(m--) { int x, y; scanf("%d%d", &x, &y); in[--y].push_back(--x); out[x].push_back(y); } std::fill(is_removed, is_removed + n, false); printf("%d\n", find_max_complexity(k)); }
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 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 | #include <algorithm> #include <cstdio> #include <vector> struct MaxCompData { MaxCompData() {} MaxCompData(int complexity_, int prev_) : complexity(complexity_), prev(prev_) {} int complexity; int prev; }; const int MAX_N = 309; int n; std::vector<int> in[MAX_N]; std::vector<int> out[MAX_N]; bool is_removed[MAX_N]; void calc_max_complexity_ending_at(const int v, int* max_complexity) { if(is_removed[v]) return; if(max_complexity[v] != -1) return; max_complexity[v] = 1; for(const auto& u : in[v]) { if(is_removed[u]) continue; if(max_complexity[u] == -1) calc_max_complexity_ending_at(u, max_complexity); max_complexity[v] = std::max(max_complexity[v], max_complexity[u] + 1); } } int calc_max_complexity() { int max_complexity[MAX_N]; std::fill(max_complexity, max_complexity + n, -1); for(int i = n-1; i >= 0; --i) { if(!is_removed[i] && max_complexity[i] == -1) calc_max_complexity_ending_at(i, max_complexity); } return std::max(*std::max_element(max_complexity, max_complexity + n), 0); } void find_path_with_max_complexity_ending_at(const int v, MaxCompData* max_complexity) { if(is_removed[v]) return; if(max_complexity[v].complexity != -1) return; max_complexity[v].complexity = 1; for(const auto& u : in[v]) { if(is_removed[u]) continue; if(max_complexity[u].complexity == -1) find_path_with_max_complexity_ending_at(u, max_complexity); if(max_complexity[v].complexity < (max_complexity[u].complexity + 1)) { max_complexity[v].complexity = max_complexity[u].complexity + 1; max_complexity[v].prev = u; } } } std::vector<int> find_path_with_max_complexity() { MaxCompData max_complexity[MAX_N]; std::fill(max_complexity, max_complexity + n, MaxCompData(-1, -1)); for(int i = n-1; i >= 0; --i) { if(!is_removed[i] && max_complexity[i].complexity == -1) find_path_with_max_complexity_ending_at(i, max_complexity); } std::vector<int> result; int result_node = -1; int max_comp = -1; for(int i = 0; i < n; ++i) { if(max_complexity[i].complexity > max_comp) { max_comp = max_complexity[i].complexity; result_node = i; } } while(result_node != -1) { result.push_back(result_node); result_node = max_complexity[result_node].prev; } return result; } int find_max_complexity(const int k) { if(k == 0) return calc_max_complexity(); int result = 1000000; const auto to_remove = find_path_with_max_complexity(); for(const auto& v : to_remove) { is_removed[v] = true; result = std::min(result, find_max_complexity(k-1)); is_removed[v] = false; } return result; } int main() { int m, k; scanf("%d%d%d", &n, &m, &k); while(m--) { int x, y; scanf("%d%d", &x, &y); in[--y].push_back(--x); out[x].push_back(y); } std::fill(is_removed, is_removed + n, false); printf("%d\n", find_max_complexity(k)); } |