#include <iostream> #include <vector> #include <queue> #define pb push_back using namespace std; typedef vector<vector<int>> graph; int main() { ios_base::sync_with_stdio(0); int n, m, k; cin >> n >> m >> k; graph g(n+2); vector<int> deg(n+1, 0); int s = 0; int a, b; for (int i = 0; i < m; i++) { cin >> a >> b; g[a].pb(b); deg[b]++; } for (int i = 1; i <= n; i++) { if (deg[i] == 0) { g[s].pb(i); deg[i]++; } } vector<int> it(k), d, used; for (int i = 1; i <= k; i++) it[k-1] = k; const int inf = 1e8; queue<int> q; int res = inf; int end = false; while (!end) { d.assign(n+1, 0); used.assign(n+1, 0); for (int i = 0; i < k; i++) d[it[i]] = inf; d[s] = -1; q.push(s); int lres = -1; while(!q.empty()) { int x = q.front(); q.pop(); if (d[x] != inf) { lres = max(lres, d[x]); if (lres >= res) { q = queue<int>(); break; } for (int y : g[x]) { d[y] = max(d[y], d[x]+1); } } for (int y : g[x]) { if (++used[y] == deg[y]) q.push(y); } } res = min(res, lres); end = true; for (int i = k-1; i >= 0; i--) { if (it[i] <= n-k+i) { it[i]++; for (int j = i+1; j < k; j++) it[j] = it[j-1]+1; end = false; break; } } } cout << res + 1 << endl; 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 | #include <iostream> #include <vector> #include <queue> #define pb push_back using namespace std; typedef vector<vector<int>> graph; int main() { ios_base::sync_with_stdio(0); int n, m, k; cin >> n >> m >> k; graph g(n+2); vector<int> deg(n+1, 0); int s = 0; int a, b; for (int i = 0; i < m; i++) { cin >> a >> b; g[a].pb(b); deg[b]++; } for (int i = 1; i <= n; i++) { if (deg[i] == 0) { g[s].pb(i); deg[i]++; } } vector<int> it(k), d, used; for (int i = 1; i <= k; i++) it[k-1] = k; const int inf = 1e8; queue<int> q; int res = inf; int end = false; while (!end) { d.assign(n+1, 0); used.assign(n+1, 0); for (int i = 0; i < k; i++) d[it[i]] = inf; d[s] = -1; q.push(s); int lres = -1; while(!q.empty()) { int x = q.front(); q.pop(); if (d[x] != inf) { lres = max(lres, d[x]); if (lres >= res) { q = queue<int>(); break; } for (int y : g[x]) { d[y] = max(d[y], d[x]+1); } } for (int y : g[x]) { if (++used[y] == deg[y]) q.push(y); } } res = min(res, lres); end = true; for (int i = k-1; i >= 0; i--) { if (it[i] <= n-k+i) { it[i]++; for (int j = i+1; j < k; j++) it[j] = it[j-1]+1; end = false; break; } } } cout << res + 1 << endl; return 0; } |