#include <vector> #include <queue> #include <algorithm> #include <stdio.h> using namespace std; #define FOR_EACH(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i) #define DBG(X) X #define NOOP(X) #define VERTEX_NUMBER_TYPE int void print_vector(vector<VERTEX_NUMBER_TYPE> v) { for (int i=0; i < v.size(); i++) { printf("%d ", v[i]); } printf("\n"); } struct Vertice { vector<VERTEX_NUMBER_TYPE> outEdges_; vector<VERTEX_NUMBER_TYPE> inEdges_; }; struct Graph { vector<Vertice> vertices_; VERTEX_NUMBER_TYPE *dist; Graph(VERTEX_NUMBER_TYPE n) { vertices_.resize(n); dist = new VERTEX_NUMBER_TYPE[n]; } ~Graph() { delete [] dist; } void addEdge(VERTEX_NUMBER_TYPE a, VERTEX_NUMBER_TYPE b) { vertices_[a].outEdges_.push_back(b); vertices_[b].inEdges_.push_back(a); } //bool forbidden1(const vector<int>& frb_vec, int v) { // return std::find(frb_vec.begin(), frb_vec.end(), v) != frb_vec.end(); //} inline bool forbidden2(VERTEX_NUMBER_TYPE frb_vec[4], VERTEX_NUMBER_TYPE v) { /*register VERTEX_NUMBER_TYPE* frb_end = frb_vec + 4; register VERTEX_NUMBER_TYPE* frb_begin = frb_vec; while (frb_begin < frb_end) { if (*frb_begin++ == v) { return true; } } return false;*/ return (v == frb_vec[0] || v == frb_vec[1] || v == frb_vec[2] || v == frb_vec[3]); } vector<VERTEX_NUMBER_TYPE> topSort(const vector<VERTEX_NUMBER_TYPE>& frb_vec) { queue<VERTEX_NUMBER_TYPE> Q; VERTEX_NUMBER_TYPE n = vertices_.size(); VERTEX_NUMBER_TYPE inDegree[n]; for(VERTEX_NUMBER_TYPE i=0; i < n; i++) { inDegree[i] = vertices_[i].inEdges_.size(); // NOOP(FOR_EACH(edge, vertices_[i].inEdges_) {if (forbidden(frb_vec, *edge)) {--inDegree[i]; });}); if(inDegree[i] == 0) { Q.push(i); } } vector<VERTEX_NUMBER_TYPE> res; while(!Q.empty()) { VERTEX_NUMBER_TYPE curr_v = Q.front(); Q.pop(); //NOOP(if (forbidden(frb_vec, curr_v)) continue;); res.emplace_back(curr_v); FOR_EACH(it, vertices_[curr_v].outEdges_) { VERTEX_NUMBER_TYPE next_v = *it; //NOOP(if (forbidden(frb_vec, next_v)) continue;); if(inDegree[next_v] > 0) { inDegree[next_v]--; if(inDegree[next_v] == 0) { Q.push(next_v); } } } } return res; } int longestPath(const vector<VERTEX_NUMBER_TYPE>& tsorted, VERTEX_NUMBER_TYPE frb_vec[4], VERTEX_NUMBER_TYPE pruningValue) { //DBG(print_vector(forbidden)); VERTEX_NUMBER_TYPE longestPath = 0; for (VERTEX_NUMBER_TYPE i=0; i < tsorted.size(); i++) { VERTEX_NUMBER_TYPE curr_v = tsorted[i]; dist[curr_v] = 0; if (forbidden2(frb_vec, curr_v)) { continue; } FOR_EACH(it, vertices_[curr_v].inEdges_) { VERTEX_NUMBER_TYPE before_v = *it; if (forbidden2(frb_vec, before_v)) { continue; } VERTEX_NUMBER_TYPE new_dist = dist[before_v] + 1; if (new_dist > dist[curr_v]) { dist[curr_v] = new_dist; } } VERTEX_NUMBER_TYPE currentDist = dist[curr_v]; if (currentDist > longestPath) { longestPath = currentDist; if (longestPath >= pruningValue) { return longestPath; } } } return longestPath; } int longestPathWithRandomKRemoved(int k, const vector<VERTEX_NUMBER_TYPE>& tsorted, VERTEX_NUMBER_TYPE frb_vec[4], VERTEX_NUMBER_TYPE currentBest) { frb_vec[0] = -1; frb_vec[1] = -1; frb_vec[2] = -1; frb_vec[3] = -1; int frb_vec_size = 0; int n = vertices_.size(); while (frb_vec_size < k) { int rv = std::rand() % n; if (!forbidden2(frb_vec, rv)) { frb_vec[frb_vec_size++] = rv; } } return longestPath(tsorted, frb_vec, currentBest-1) + 1; } }; int main() { std::srand(0); int n,m,k; scanf("%d%d%d", &n, &m, &k); Graph G(n); for (int i=0; i < m; i++) { int x,y; scanf("%d%d", &x, &y); G.addEdge(x-1,y-1); } if (k >= n) { printf("0\n"); return 0; } VERTEX_NUMBER_TYPE frb_vec_memholder[4]; for (int i=0; i < 4; i++) frb_vec_memholder[i] = -1; vector<VERTEX_NUMBER_TYPE> tsorted = G.topSort(vector<VERTEX_NUMBER_TYPE>{}); // print_vector(tsorted); int initialLongestPath = G.longestPath(tsorted, frb_vec_memholder, 30000) + 1; if (k == 0) { printf("%d\n", initialLongestPath); return 0; } int bestRes = initialLongestPath; for (int i=0; i < 500000; i++) { int res = G.longestPathWithRandomKRemoved(k, tsorted, frb_vec_memholder, bestRes); bestRes = min(bestRes, res); //printf("longestRandom=%d best=%d\n", res, bestRes); } printf("%d\n", bestRes); 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 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 | #include <vector> #include <queue> #include <algorithm> #include <stdio.h> using namespace std; #define FOR_EACH(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i) #define DBG(X) X #define NOOP(X) #define VERTEX_NUMBER_TYPE int void print_vector(vector<VERTEX_NUMBER_TYPE> v) { for (int i=0; i < v.size(); i++) { printf("%d ", v[i]); } printf("\n"); } struct Vertice { vector<VERTEX_NUMBER_TYPE> outEdges_; vector<VERTEX_NUMBER_TYPE> inEdges_; }; struct Graph { vector<Vertice> vertices_; VERTEX_NUMBER_TYPE *dist; Graph(VERTEX_NUMBER_TYPE n) { vertices_.resize(n); dist = new VERTEX_NUMBER_TYPE[n]; } ~Graph() { delete [] dist; } void addEdge(VERTEX_NUMBER_TYPE a, VERTEX_NUMBER_TYPE b) { vertices_[a].outEdges_.push_back(b); vertices_[b].inEdges_.push_back(a); } //bool forbidden1(const vector<int>& frb_vec, int v) { // return std::find(frb_vec.begin(), frb_vec.end(), v) != frb_vec.end(); //} inline bool forbidden2(VERTEX_NUMBER_TYPE frb_vec[4], VERTEX_NUMBER_TYPE v) { /*register VERTEX_NUMBER_TYPE* frb_end = frb_vec + 4; register VERTEX_NUMBER_TYPE* frb_begin = frb_vec; while (frb_begin < frb_end) { if (*frb_begin++ == v) { return true; } } return false;*/ return (v == frb_vec[0] || v == frb_vec[1] || v == frb_vec[2] || v == frb_vec[3]); } vector<VERTEX_NUMBER_TYPE> topSort(const vector<VERTEX_NUMBER_TYPE>& frb_vec) { queue<VERTEX_NUMBER_TYPE> Q; VERTEX_NUMBER_TYPE n = vertices_.size(); VERTEX_NUMBER_TYPE inDegree[n]; for(VERTEX_NUMBER_TYPE i=0; i < n; i++) { inDegree[i] = vertices_[i].inEdges_.size(); // NOOP(FOR_EACH(edge, vertices_[i].inEdges_) {if (forbidden(frb_vec, *edge)) {--inDegree[i]; });}); if(inDegree[i] == 0) { Q.push(i); } } vector<VERTEX_NUMBER_TYPE> res; while(!Q.empty()) { VERTEX_NUMBER_TYPE curr_v = Q.front(); Q.pop(); //NOOP(if (forbidden(frb_vec, curr_v)) continue;); res.emplace_back(curr_v); FOR_EACH(it, vertices_[curr_v].outEdges_) { VERTEX_NUMBER_TYPE next_v = *it; //NOOP(if (forbidden(frb_vec, next_v)) continue;); if(inDegree[next_v] > 0) { inDegree[next_v]--; if(inDegree[next_v] == 0) { Q.push(next_v); } } } } return res; } int longestPath(const vector<VERTEX_NUMBER_TYPE>& tsorted, VERTEX_NUMBER_TYPE frb_vec[4], VERTEX_NUMBER_TYPE pruningValue) { //DBG(print_vector(forbidden)); VERTEX_NUMBER_TYPE longestPath = 0; for (VERTEX_NUMBER_TYPE i=0; i < tsorted.size(); i++) { VERTEX_NUMBER_TYPE curr_v = tsorted[i]; dist[curr_v] = 0; if (forbidden2(frb_vec, curr_v)) { continue; } FOR_EACH(it, vertices_[curr_v].inEdges_) { VERTEX_NUMBER_TYPE before_v = *it; if (forbidden2(frb_vec, before_v)) { continue; } VERTEX_NUMBER_TYPE new_dist = dist[before_v] + 1; if (new_dist > dist[curr_v]) { dist[curr_v] = new_dist; } } VERTEX_NUMBER_TYPE currentDist = dist[curr_v]; if (currentDist > longestPath) { longestPath = currentDist; if (longestPath >= pruningValue) { return longestPath; } } } return longestPath; } int longestPathWithRandomKRemoved(int k, const vector<VERTEX_NUMBER_TYPE>& tsorted, VERTEX_NUMBER_TYPE frb_vec[4], VERTEX_NUMBER_TYPE currentBest) { frb_vec[0] = -1; frb_vec[1] = -1; frb_vec[2] = -1; frb_vec[3] = -1; int frb_vec_size = 0; int n = vertices_.size(); while (frb_vec_size < k) { int rv = std::rand() % n; if (!forbidden2(frb_vec, rv)) { frb_vec[frb_vec_size++] = rv; } } return longestPath(tsorted, frb_vec, currentBest-1) + 1; } }; int main() { std::srand(0); int n,m,k; scanf("%d%d%d", &n, &m, &k); Graph G(n); for (int i=0; i < m; i++) { int x,y; scanf("%d%d", &x, &y); G.addEdge(x-1,y-1); } if (k >= n) { printf("0\n"); return 0; } VERTEX_NUMBER_TYPE frb_vec_memholder[4]; for (int i=0; i < 4; i++) frb_vec_memholder[i] = -1; vector<VERTEX_NUMBER_TYPE> tsorted = G.topSort(vector<VERTEX_NUMBER_TYPE>{}); // print_vector(tsorted); int initialLongestPath = G.longestPath(tsorted, frb_vec_memholder, 30000) + 1; if (k == 0) { printf("%d\n", initialLongestPath); return 0; } int bestRes = initialLongestPath; for (int i=0; i < 500000; i++) { int res = G.longestPathWithRandomKRemoved(k, tsorted, frb_vec_memholder, bestRes); bestRes = min(bestRes, res); //printf("longestRandom=%d best=%d\n", res, bestRes); } printf("%d\n", bestRes); return 0; } |