#include <bits/stdc++.h> #define fi first #define se second #define pb push_back //#define cerr if(0)cout using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef long double ld; typedef vector<int> vi; typedef vector<ll> vll; const int duzo = 769; int n, m, st[duzo]; int nn = duzo; vector<int> g[duzo], gt[duzo]; vector<int> wyje; int dlug[duzo]; bool jest(int x) { for(auto y: wyje) if(x == y) return false; return true; } void usun() { for(auto w: wyje) for(auto x: g[w]) --st[x]; } void napraw_stopnie() { for(int i = 1; i <= n; ++i) st[i] = gt[i].size(); } int solve() { usun(); queue<int> kol; for(int i = 1; i <= n; ++i) { if(st[i] == 0 && jest(i)) { kol.push(i); } } int ret = 0; while(!kol.empty()) { int ziom = kol.front(); kol.pop(); dlug[ziom] = 1; for(auto x: gt[ziom]) if(jest(x)) dlug[ziom] = max(dlug[ziom], dlug[x] + 1); ret = max(ret, dlug[ziom]); for(auto x: g[ziom]) if(jest(x)) { --st[x]; if(st[x] == 0) kol.push(x); } } napraw_stopnie(); return ret; } void iteruj(int lev, int od) { if(lev == 0) { int rob = solve(); nn = min(nn, solve()); /*cerr << rob << ": "; for(auto x: wyje) cerr << x << " "; cerr << "\n";*/ return; } for(int i = od; i <= n; ++i) { wyje.pb(i); iteruj(lev - 1, i + 1); wyje.pop_back(); } } int main() { ios_base::sync_with_stdio(0); // cin.tie(0); int k, u, v; cin >> n >> m >> k; for(int i = 1; i <= m; ++i) { cin >> u >> v; g[u].pb(v); gt[v].pb(u); ++st[v]; } iteruj(k, 1); cout << nn; 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 | #include <bits/stdc++.h> #define fi first #define se second #define pb push_back //#define cerr if(0)cout using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef long double ld; typedef vector<int> vi; typedef vector<ll> vll; const int duzo = 769; int n, m, st[duzo]; int nn = duzo; vector<int> g[duzo], gt[duzo]; vector<int> wyje; int dlug[duzo]; bool jest(int x) { for(auto y: wyje) if(x == y) return false; return true; } void usun() { for(auto w: wyje) for(auto x: g[w]) --st[x]; } void napraw_stopnie() { for(int i = 1; i <= n; ++i) st[i] = gt[i].size(); } int solve() { usun(); queue<int> kol; for(int i = 1; i <= n; ++i) { if(st[i] == 0 && jest(i)) { kol.push(i); } } int ret = 0; while(!kol.empty()) { int ziom = kol.front(); kol.pop(); dlug[ziom] = 1; for(auto x: gt[ziom]) if(jest(x)) dlug[ziom] = max(dlug[ziom], dlug[x] + 1); ret = max(ret, dlug[ziom]); for(auto x: g[ziom]) if(jest(x)) { --st[x]; if(st[x] == 0) kol.push(x); } } napraw_stopnie(); return ret; } void iteruj(int lev, int od) { if(lev == 0) { int rob = solve(); nn = min(nn, solve()); /*cerr << rob << ": "; for(auto x: wyje) cerr << x << " "; cerr << "\n";*/ return; } for(int i = od; i <= n; ++i) { wyje.pb(i); iteruj(lev - 1, i + 1); wyje.pop_back(); } } int main() { ios_base::sync_with_stdio(0); // cin.tie(0); int k, u, v; cin >> n >> m >> k; for(int i = 1; i <= m; ++i) { cin >> u >> v; g[u].pb(v); gt[v].pb(u); ++st[v]; } iteruj(k, 1); cout << nn; return 0; } |