#include<bits/stdc++.h> using namespace std; typedef long long int lld; struct Graph{ vector<int> path; int dist; bool lock; Graph(void): dist(0), lock(false) {} }; vector<Graph> g; void clear(void){ for(auto& i : g) i.dist = 1; } int check(void){ clear(); int r = 0; for(int i=0;i<g.size();i++){ if(g[i].lock) continue; r = max(r, g[i].dist); for(int u : g[i].path) g[u].dist = max(g[u].dist, g[i].dist+1); } return r; } vector<bool> M; int res; int tmp; void gen(int k){ if(k == 0){ int v = check(); if(tmp > v){ tmp = v; for(int i=0;i<M.size();i++) M[i] = g[i].lock; } return; } for(int i=0;i<g.size();i++) if(!g[i].lock){ g[i].lock = true; gen(k-1); g[i].lock = false; } return; } void calc(vector<int>& t){ fill(M.begin(), M.end(), false); for(auto& i : g) i.lock = false; tmp = g.size(); for(int i : t){ gen(i); for(int j=0;j<g.size();j++) g[j].lock = M[j]; } res = min(res, tmp); } vector<vector<int> > t[5]; int main(void){ ios_base::sync_with_stdio(false); lld n,m,k; cin >> n >> m >> k; g.resize(n); M.resize(n); for(int i=0;i<m;i++){ int a,b; cin >> a >> b; a--, b--; g[a].path.push_back(b); } t[1].push_back({1}); t[2].push_back({2}); t[3].push_back({1,1,1}); t[3].push_back({1,2}); t[3].push_back({2,1}); t[4].push_back({1,1,1,1}); t[4].push_back({2,1,1}); t[4].push_back({1,2,1}); t[4].push_back({1,1,2}); t[4].push_back({2,2}); if(pow(n,k)*n <= 1e8){ vector<int> t; t.push_back(k); res = n; calc(t); }else{ res = n; for(auto& i : t[k]) calc(i); } 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 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 | #include<bits/stdc++.h> using namespace std; typedef long long int lld; struct Graph{ vector<int> path; int dist; bool lock; Graph(void): dist(0), lock(false) {} }; vector<Graph> g; void clear(void){ for(auto& i : g) i.dist = 1; } int check(void){ clear(); int r = 0; for(int i=0;i<g.size();i++){ if(g[i].lock) continue; r = max(r, g[i].dist); for(int u : g[i].path) g[u].dist = max(g[u].dist, g[i].dist+1); } return r; } vector<bool> M; int res; int tmp; void gen(int k){ if(k == 0){ int v = check(); if(tmp > v){ tmp = v; for(int i=0;i<M.size();i++) M[i] = g[i].lock; } return; } for(int i=0;i<g.size();i++) if(!g[i].lock){ g[i].lock = true; gen(k-1); g[i].lock = false; } return; } void calc(vector<int>& t){ fill(M.begin(), M.end(), false); for(auto& i : g) i.lock = false; tmp = g.size(); for(int i : t){ gen(i); for(int j=0;j<g.size();j++) g[j].lock = M[j]; } res = min(res, tmp); } vector<vector<int> > t[5]; int main(void){ ios_base::sync_with_stdio(false); lld n,m,k; cin >> n >> m >> k; g.resize(n); M.resize(n); for(int i=0;i<m;i++){ int a,b; cin >> a >> b; a--, b--; g[a].path.push_back(b); } t[1].push_back({1}); t[2].push_back({2}); t[3].push_back({1,1,1}); t[3].push_back({1,2}); t[3].push_back({2,1}); t[4].push_back({1,1,1,1}); t[4].push_back({2,1,1}); t[4].push_back({1,2,1}); t[4].push_back({1,1,2}); t[4].push_back({2,2}); if(pow(n,k)*n <= 1e8){ vector<int> t; t.push_back(k); res = n; calc(t); }else{ res = n; for(auto& i : t[k]) calc(i); } cout << res << "\n"; return 0; } |