#include <iostream> #include <vector> using namespace std; const int N = 301; int n, res = 300; vector<int> v[N]; pair<int, int> longest[N]; bool removed[N]; void rec_solve(int k) { pair<int, int> best; for (int i=1; i<=n; i++) longest[i] = make_pair(1, 0); for (int i=1; i<=n; i++) { if (removed[i]) continue; best = max(best, make_pair(longest[i].first, i)); for (int x: v[i]) longest[x] = max(longest[x], make_pair(longest[i].first+1, i)); } res = min(res, best.first); if (k > 0) { vector<int> path; int x = best.second; while (x) { path.push_back(x); x = longest[x].second; } for (int x: path) { removed[x] = true; rec_solve(k-1); removed[x] = false; } } } int main() { ios_base::sync_with_stdio(0); int m, k, x, y; cin >> n >> m >> k; if (k >= n) { printf("0\n"); return 0; } while (m--) { cin >> x >> y; v[x].push_back(y); } rec_solve(k); cout << res << "\n"; 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 | #include <iostream> #include <vector> using namespace std; const int N = 301; int n, res = 300; vector<int> v[N]; pair<int, int> longest[N]; bool removed[N]; void rec_solve(int k) { pair<int, int> best; for (int i=1; i<=n; i++) longest[i] = make_pair(1, 0); for (int i=1; i<=n; i++) { if (removed[i]) continue; best = max(best, make_pair(longest[i].first, i)); for (int x: v[i]) longest[x] = max(longest[x], make_pair(longest[i].first+1, i)); } res = min(res, best.first); if (k > 0) { vector<int> path; int x = best.second; while (x) { path.push_back(x); x = longest[x].second; } for (int x: path) { removed[x] = true; rec_solve(k-1); removed[x] = false; } } } int main() { ios_base::sync_with_stdio(0); int m, k, x, y; cin >> n >> m >> k; if (k >= n) { printf("0\n"); return 0; } while (m--) { cin >> x >> y; v[x].push_back(y); } rec_solve(k); cout << res << "\n"; return 0; } |