#include <algorithm> #include <iostream> #include <vector> using namespace std; struct Vertex { vector<int> links; int value = -1; int bestNext = -1; bool removed = false; void clearCache() { value = bestNext = -1; } }; class Solution { private: int n, m, k; vector<Vertex> vertexMap; int getVertexIdWithLongestPath() { int resultId = -1, resultValue = 0; for (int id = 0; id < vertexMap.size(); id++) { int value = getVertexValue(id); if (value == -1) continue; if (resultId == -1 || value > resultValue) { resultId = id; resultValue = value; } } return resultId; } int getVertexIdWithLongestPath(const vector<int>& idSubset) { int resultId = -1, resultValue = 0; for (int id : idSubset) { int value = getVertexValue(id); if (value == -1) continue; if (resultId == -1 || value > resultValue) { resultId = id; resultValue = value; } } return resultId; } int getVertexValue(int id) { Vertex& v = vertexMap[id]; if (v.removed) return -1; if (v.value == -1) { v.bestNext = getVertexIdWithLongestPath(v.links); v.value = v.bestNext == -1 ? 0 : vertexMap[v.bestNext].value + 1; } return v.value; } void clearCache() { for (int id = 0; id < vertexMap.size(); id++) vertexMap[id].clearCache(); } void expandPath(int fromId, vector<int>& result) { result.clear(); if (fromId < 0) return; result.reserve(vertexMap[fromId].value); for (int id = fromId; id != -1; id = vertexMap[id].bestNext) result.push_back(id); } int alternativeLength(int id, int bestId) { Vertex& v = vertexMap[id]; int altVal = 0; for (int linkId : v.links) { if (linkId == bestId) continue; int val = getVertexValue(linkId); if (val > altVal) altVal = val + 1; } return altVal; } int solve(int removeCount) { int startId = getVertexIdWithLongestPath(); if (startId == -1) return 0; int result = vertexMap[startId].value + 1; if (removeCount > 0) { vector<int> path; expandPath(startId, path); vector<vector<int>> altLengths(n + 1); altLengths[path.size() - 1].push_back(path[0]); for (int id, len, i = 1; i < path.size(); i++) { id = path[i]; len = max<int>(path.size() - i - 1, i + alternativeLength(id - 1, id)); altLengths[len].push_back(id); } for (int i = 0; i < altLengths.size(); i++) { if (i >= result) break; for (int id : altLengths[i]) { vertexMap[id].removed = true; clearCache(); int subResult = solve(removeCount - 1); if (subResult < result) result = subResult; vertexMap[id].removed = false; } } } return result; } public: void readInput() { cin >> n; cin >> m; cin >> k; vertexMap.resize(n); for (int from, to, i = 0; i < m; i++) { cin >> from; cin >> to; vertexMap[from - 1].links.push_back(to - 1); } } int solve() { return solve(k); } }; int main(void) { Solution solution; solution.readInput(); cout << solution.solve(); 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 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 | #include <algorithm> #include <iostream> #include <vector> using namespace std; struct Vertex { vector<int> links; int value = -1; int bestNext = -1; bool removed = false; void clearCache() { value = bestNext = -1; } }; class Solution { private: int n, m, k; vector<Vertex> vertexMap; int getVertexIdWithLongestPath() { int resultId = -1, resultValue = 0; for (int id = 0; id < vertexMap.size(); id++) { int value = getVertexValue(id); if (value == -1) continue; if (resultId == -1 || value > resultValue) { resultId = id; resultValue = value; } } return resultId; } int getVertexIdWithLongestPath(const vector<int>& idSubset) { int resultId = -1, resultValue = 0; for (int id : idSubset) { int value = getVertexValue(id); if (value == -1) continue; if (resultId == -1 || value > resultValue) { resultId = id; resultValue = value; } } return resultId; } int getVertexValue(int id) { Vertex& v = vertexMap[id]; if (v.removed) return -1; if (v.value == -1) { v.bestNext = getVertexIdWithLongestPath(v.links); v.value = v.bestNext == -1 ? 0 : vertexMap[v.bestNext].value + 1; } return v.value; } void clearCache() { for (int id = 0; id < vertexMap.size(); id++) vertexMap[id].clearCache(); } void expandPath(int fromId, vector<int>& result) { result.clear(); if (fromId < 0) return; result.reserve(vertexMap[fromId].value); for (int id = fromId; id != -1; id = vertexMap[id].bestNext) result.push_back(id); } int alternativeLength(int id, int bestId) { Vertex& v = vertexMap[id]; int altVal = 0; for (int linkId : v.links) { if (linkId == bestId) continue; int val = getVertexValue(linkId); if (val > altVal) altVal = val + 1; } return altVal; } int solve(int removeCount) { int startId = getVertexIdWithLongestPath(); if (startId == -1) return 0; int result = vertexMap[startId].value + 1; if (removeCount > 0) { vector<int> path; expandPath(startId, path); vector<vector<int>> altLengths(n + 1); altLengths[path.size() - 1].push_back(path[0]); for (int id, len, i = 1; i < path.size(); i++) { id = path[i]; len = max<int>(path.size() - i - 1, i + alternativeLength(id - 1, id)); altLengths[len].push_back(id); } for (int i = 0; i < altLengths.size(); i++) { if (i >= result) break; for (int id : altLengths[i]) { vertexMap[id].removed = true; clearCache(); int subResult = solve(removeCount - 1); if (subResult < result) result = subResult; vertexMap[id].removed = false; } } } return result; } public: void readInput() { cin >> n; cin >> m; cin >> k; vertexMap.resize(n); for (int from, to, i = 0; i < m; i++) { cin >> from; cin >> to; vertexMap[from - 1].links.push_back(to - 1); } } int solve() { return solve(k); } }; int main(void) { Solution solution; solution.readInput(); cout << solution.solve(); return 0; } |