#include <bits/stdc++.h> using namespace std; const int N = 301; vector<int> G[N]; vector<int> R(N); int n, m, k; int T[4]; int dfs_1(int u) { R[u] = 1; for (int v : G[u]) { bool ban = false; for (int i = 0; i < k; i++) if (v == T[i]) ban = true; if (!ban) { if (R[v] == -1) dfs_1(v); R[u] = max(R[u], R[v] + 1); } } return R[u]; } int main() { srand(time(0)); ios_base::sync_with_stdio(false); cin >> n >> m >> k; while (m--) { int a, s; cin >> a >> s; G[a].push_back(s); } if (k == n) { cout << 0 << endl; return 0; } if (k == n - 1) { cout << 1 << endl; return 0; } if (k == 0) { for (int i = 1; i <= n; i++) R[i] = -1; for (int i = 1; i <= n; i++) if (R[i] == -1) dfs_1(i); int res = -1; for (int i = 1; i <= n; i++) res = max(res, R[i]); cout << res << endl; return 0; } if (k == 1) { int res = 2e9; for (int i = 1; i <= n; i++) { T[0] = i; for (int j = 1; j <= n; j++) R[j] = -1; for (int j = 1; j <= n; j++) if (R[j] == -1 && j != i) dfs_1(j); int tmp_r = -1; for (int j = 1; j <= n; j++) tmp_r = max(tmp_r, R[j]); res = min(res, tmp_r); } cout << res << endl; return 0; } if (k == 2) { int res = 2e9; for (int i = 1; i <= n; i++) { T[0] = i; for (int j = i + 1; j <= n; j++) { T[1] = j; for (int l = 1; l <= n; l++) R[l] = -1; for (int l = 1; l <= n; l++) if (R[l] == -1 && l != i && l != j) dfs_1(l); int tmp_r = -1; for (int l = 1; l <= n; l++) tmp_r = max(tmp_r, R[l]); res = min(res, tmp_r); } } cout << res << endl; return 0; } vector<int> V(n); for (int i = 0; i < n; i++) V[i] = i + 1; for (int i = n / 8; i < n - n / 8; i++) V.push_back(i); for (int i = n / 6; i < n - n / 6; i++) V.push_back(i); random_shuffle(V.begin(), V.end()); int qwe = V.size(); int ile = 150000 / k; int res = 2e9; while (ile--) { for (int i = 0; i < k; i++) { T[i] = V[rand() % qwe]; for (int j = 0; j < i; j++) if (T[i] == T[j]) i--; } for (int i = 1; i <= n; i++) R[i] = -1; for (int i = 1; i <= n; i++) { bool ban = false; for (int j = 0; j < k; j++) if (i == T[j]) ban = true; if (R[i] == -1 && !ban) dfs_1(i); } int tmp_r = -1; for (int i = 1; i <= n; i++) tmp_r = max(tmp_r, R[i]); res = min(res, tmp_r); } cout << res << 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 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 | #include <bits/stdc++.h> using namespace std; const int N = 301; vector<int> G[N]; vector<int> R(N); int n, m, k; int T[4]; int dfs_1(int u) { R[u] = 1; for (int v : G[u]) { bool ban = false; for (int i = 0; i < k; i++) if (v == T[i]) ban = true; if (!ban) { if (R[v] == -1) dfs_1(v); R[u] = max(R[u], R[v] + 1); } } return R[u]; } int main() { srand(time(0)); ios_base::sync_with_stdio(false); cin >> n >> m >> k; while (m--) { int a, s; cin >> a >> s; G[a].push_back(s); } if (k == n) { cout << 0 << endl; return 0; } if (k == n - 1) { cout << 1 << endl; return 0; } if (k == 0) { for (int i = 1; i <= n; i++) R[i] = -1; for (int i = 1; i <= n; i++) if (R[i] == -1) dfs_1(i); int res = -1; for (int i = 1; i <= n; i++) res = max(res, R[i]); cout << res << endl; return 0; } if (k == 1) { int res = 2e9; for (int i = 1; i <= n; i++) { T[0] = i; for (int j = 1; j <= n; j++) R[j] = -1; for (int j = 1; j <= n; j++) if (R[j] == -1 && j != i) dfs_1(j); int tmp_r = -1; for (int j = 1; j <= n; j++) tmp_r = max(tmp_r, R[j]); res = min(res, tmp_r); } cout << res << endl; return 0; } if (k == 2) { int res = 2e9; for (int i = 1; i <= n; i++) { T[0] = i; for (int j = i + 1; j <= n; j++) { T[1] = j; for (int l = 1; l <= n; l++) R[l] = -1; for (int l = 1; l <= n; l++) if (R[l] == -1 && l != i && l != j) dfs_1(l); int tmp_r = -1; for (int l = 1; l <= n; l++) tmp_r = max(tmp_r, R[l]); res = min(res, tmp_r); } } cout << res << endl; return 0; } vector<int> V(n); for (int i = 0; i < n; i++) V[i] = i + 1; for (int i = n / 8; i < n - n / 8; i++) V.push_back(i); for (int i = n / 6; i < n - n / 6; i++) V.push_back(i); random_shuffle(V.begin(), V.end()); int qwe = V.size(); int ile = 150000 / k; int res = 2e9; while (ile--) { for (int i = 0; i < k; i++) { T[i] = V[rand() % qwe]; for (int j = 0; j < i; j++) if (T[i] == T[j]) i--; } for (int i = 1; i <= n; i++) R[i] = -1; for (int i = 1; i <= n; i++) { bool ban = false; for (int j = 0; j < k; j++) if (i == T[j]) ban = true; if (R[i] == -1 && !ban) dfs_1(i); } int tmp_r = -1; for (int i = 1; i <= n; i++) tmp_r = max(tmp_r, R[i]); res = min(res, tmp_r); } cout << res << endl; return 0; } |