#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; #define fir first #define sec second typedef vector<int> vi; #define pb push_back #define ppb pop_back #define empb emplace_back #define N 320 #define M 400 int n, m, k, ans; int dp[N]; int dout[N]; vi in[N]; //vi out[N]; void dfs(int i = 0, int c = 0, int res = 0) { if (i == n) { ans = min(ans, res); return; } if (res >= ans) return; dp[i] = 0; if (c < k && dout[i] != 0) dfs(i+1, c+1, res); for (int j : in[i]) dp[i] = max(dp[i], dp[j]); dfs(i+1, c, max(res, ++dp[i])); if (c < k && dout[i] == 0) dfs(i+1, c+1, res); } /*void sfd(int i, int c = 0, int res = 0) { if (i < 0) { ans = min(ans, res); return; } if (res >= ans) return; dp[i] = 0; if (c < k) sfd(i-1, c+1, res); for (int j : out[i]) dp[i] = max(dp[i], dp[j]); sfd(i-1, c, max(res, ++dp[i])); }*/ int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n >> m >> k; ans = n; if (k == n) return cout << "0\n", 0; if (k == n-1) return cout << "1\n", 0; if (m == n*(n-1)/2) return cout << n-k << '\n', 0; for (int i = 0; i < m; ++i) { int x, y; cin >> x >> y; --x; --y; //out[x].pb(y); ++dout[x]; in[y].pb(x); } for (int i = 0; i < n; ++i) { sort(in[i].begin(), in[i].end()); //sort(out[i].begin(), out[i].end()); } dfs(); //sfd(n-1); cout << ans << '\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 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 | #include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; #define fir first #define sec second typedef vector<int> vi; #define pb push_back #define ppb pop_back #define empb emplace_back #define N 320 #define M 400 int n, m, k, ans; int dp[N]; int dout[N]; vi in[N]; //vi out[N]; void dfs(int i = 0, int c = 0, int res = 0) { if (i == n) { ans = min(ans, res); return; } if (res >= ans) return; dp[i] = 0; if (c < k && dout[i] != 0) dfs(i+1, c+1, res); for (int j : in[i]) dp[i] = max(dp[i], dp[j]); dfs(i+1, c, max(res, ++dp[i])); if (c < k && dout[i] == 0) dfs(i+1, c+1, res); } /*void sfd(int i, int c = 0, int res = 0) { if (i < 0) { ans = min(ans, res); return; } if (res >= ans) return; dp[i] = 0; if (c < k) sfd(i-1, c+1, res); for (int j : out[i]) dp[i] = max(dp[i], dp[j]); sfd(i-1, c, max(res, ++dp[i])); }*/ int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n >> m >> k; ans = n; if (k == n) return cout << "0\n", 0; if (k == n-1) return cout << "1\n", 0; if (m == n*(n-1)/2) return cout << n-k << '\n', 0; for (int i = 0; i < m; ++i) { int x, y; cin >> x >> y; --x; --y; //out[x].pb(y); ++dout[x]; in[y].pb(x); } for (int i = 0; i < n; ++i) { sort(in[i].begin(), in[i].end()); //sort(out[i].begin(), out[i].end()); } dfs(); //sfd(n-1); cout << ans << '\n'; return 0; } |