#include <iostream> #include <vector> using namespace std; void DFS (vector < vector <int> > &g,vector < int > &deq, vector <int> &odp, int s) { int wyn=odp[s]+1; for (int i=0;i<g[s].size();++i) { int x=g[s][i]; if (odp[x]<wyn) odp[x]=wyn; --deq[x]; if (deq[x]==0) DFS(g,deq,odp,x); } } int n,m,k,a,b,wynik,ww; int main() { cin>>n >> m >> k; vector < vector <int> > g (n+1); vector < int > stop_w (n+1); for (int i=0;i<m;++i) { cin >> a >> b; g[a].push_back(b); stop_w[b]++; } vector <int> odp (n+1,1); if (k==0) { for (int i=1;i<=n;++i) if (stop_w[i]==0) DFS(g,stop_w,odp,i); wynik=0; for (int i=1;i<=n;++i) if (odp[i]>wynik) wynik=odp[i]; cout << wynik; return 0; } if (k==1) { vector <int> s=stop_w; wynik=1000; for (int v=1;v<=n;++v) { s[v]=-1; for (int i=0;i<g[v].size();++i) s[g[v][i]]--; vector <int> _s=s; ww=0; for (int i=1;i<=n;++i) odp[i]=1; for (int j=1;j<=n;++j) if (s[j]==0) DFS(g,_s,odp,j); for (int i=1;i<=n;++i) if (s[i]!=-1&&odp[i]>ww) ww=odp[i]; if (ww<wynik) wynik=ww; s[v]=stop_w[v]; for (int i=0;i<g[v].size();++i) s[g[v][i]]++; } cout << wynik; return 0; } if (k==2) { vector <int> s=stop_w; wynik=1000; for (int v=1;v<=n;++v) { s[v]=-1; for (int i=0;i<g[v].size();++i) s[g[v][i]]--; for (int p=v+1;p<=n;++p) { s[p]=-1; for (int i=0;i<g[p].size();++i) s[g[p][i]]--; vector <int> _s=s; ww=0; for (int i=1;i<=n;++i) odp[i]=1; for (int j=1;j<=n;++j) if (s[j]==0) DFS(g,_s,odp,j); for (int i=1;i<=n;++i) if (s[i]!=-1&&odp[i]>ww) ww=odp[i]; if (ww<wynik) wynik=ww; s[p]=stop_w[p]; for (int i=0;i<g[p].size();++i) s[g[p][i]]++; } s[v]=stop_w[v]; for (int i=0;i<g[v].size();++i) s[g[v][i]]++; } cout << wynik; return 0; } if (k==3) { vector <int> s=stop_w; wynik=1000; for (int v=1;v<=n;++v) { s[v]=-1; for (int i=0;i<g[v].size();++i) s[g[v][i]]--; for (int q=v+1;q<=n;++q) { s[q]=-1; for (int i=0;i<g[q].size();++i) s[g[q][i]]--; for (int p=q+1;p<=n;++p) { s[p]=-1; for (int i=0;i<g[p].size();++i) s[g[p][i]]--; vector <int> _s=s; ww=0; for (int i=1;i<=n;++i) odp[i]=1; for (int j=1;j<=n;++j) if (s[j]==0) DFS(g,_s,odp,j); for (int i=1;i<=n;++i) if (s[i]!=-1&&odp[i]>ww) ww=odp[i]; if (ww<wynik) wynik=ww; s[p]=stop_w[p]; for (int i=0;i<g[p].size();++i) s[g[p][i]]++; } s[q]=stop_w[q]; for (int i=0;i<g[q].size();++i) s[g[q][i]]++; } s[v]=stop_w[v]; for (int i=0;i<g[v].size();++i) s[g[v][i]]++; } cout << wynik; return 0; } vector <int> s=stop_w; wynik=1000; for (int v=1;v<=n;++v) { s[v]=-1; for (int i=0;i<g[v].size();++i) s[g[v][i]]--; for (int d=v+1;d<=n;++d) { s[d]=-1; for (int i=0;i<g[d].size();++i) s[g[d][i]]--; for (int q=d+1;q<=n;++q) { s[q]=-1; for (int i=0;i<g[q].size();++i) s[g[q][i]]--; for (int p=q+1;p<=n;++p) { s[p]=-1; for (int i=0;i<g[p].size();++i) s[g[p][i]]--; vector <int> _s=s; ww=0; for (int i=1;i<=n;++i) odp[i]=1; for (int j=1;j<=n;++j) if (s[j]==0) DFS(g,_s,odp,j); for (int i=1;i<=n;++i) if (s[i]!=-1&&odp[i]>ww) ww=odp[i]; if (ww<wynik) wynik=ww; s[p]=stop_w[p]; for (int i=0;i<g[p].size();++i) s[g[p][i]]++; } s[q]=stop_w[q]; for (int i=0;i<g[q].size();++i) s[g[q][i]]++; } s[d]=stop_w[d]; for (int i=0;i<g[d].size();++i) s[g[d][i]]++; } s[v]=stop_w[v]; for (int i=0;i<g[v].size();++i) s[g[v][i]]++; } cout << wynik; 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 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 | #include <iostream> #include <vector> using namespace std; void DFS (vector < vector <int> > &g,vector < int > &deq, vector <int> &odp, int s) { int wyn=odp[s]+1; for (int i=0;i<g[s].size();++i) { int x=g[s][i]; if (odp[x]<wyn) odp[x]=wyn; --deq[x]; if (deq[x]==0) DFS(g,deq,odp,x); } } int n,m,k,a,b,wynik,ww; int main() { cin>>n >> m >> k; vector < vector <int> > g (n+1); vector < int > stop_w (n+1); for (int i=0;i<m;++i) { cin >> a >> b; g[a].push_back(b); stop_w[b]++; } vector <int> odp (n+1,1); if (k==0) { for (int i=1;i<=n;++i) if (stop_w[i]==0) DFS(g,stop_w,odp,i); wynik=0; for (int i=1;i<=n;++i) if (odp[i]>wynik) wynik=odp[i]; cout << wynik; return 0; } if (k==1) { vector <int> s=stop_w; wynik=1000; for (int v=1;v<=n;++v) { s[v]=-1; for (int i=0;i<g[v].size();++i) s[g[v][i]]--; vector <int> _s=s; ww=0; for (int i=1;i<=n;++i) odp[i]=1; for (int j=1;j<=n;++j) if (s[j]==0) DFS(g,_s,odp,j); for (int i=1;i<=n;++i) if (s[i]!=-1&&odp[i]>ww) ww=odp[i]; if (ww<wynik) wynik=ww; s[v]=stop_w[v]; for (int i=0;i<g[v].size();++i) s[g[v][i]]++; } cout << wynik; return 0; } if (k==2) { vector <int> s=stop_w; wynik=1000; for (int v=1;v<=n;++v) { s[v]=-1; for (int i=0;i<g[v].size();++i) s[g[v][i]]--; for (int p=v+1;p<=n;++p) { s[p]=-1; for (int i=0;i<g[p].size();++i) s[g[p][i]]--; vector <int> _s=s; ww=0; for (int i=1;i<=n;++i) odp[i]=1; for (int j=1;j<=n;++j) if (s[j]==0) DFS(g,_s,odp,j); for (int i=1;i<=n;++i) if (s[i]!=-1&&odp[i]>ww) ww=odp[i]; if (ww<wynik) wynik=ww; s[p]=stop_w[p]; for (int i=0;i<g[p].size();++i) s[g[p][i]]++; } s[v]=stop_w[v]; for (int i=0;i<g[v].size();++i) s[g[v][i]]++; } cout << wynik; return 0; } if (k==3) { vector <int> s=stop_w; wynik=1000; for (int v=1;v<=n;++v) { s[v]=-1; for (int i=0;i<g[v].size();++i) s[g[v][i]]--; for (int q=v+1;q<=n;++q) { s[q]=-1; for (int i=0;i<g[q].size();++i) s[g[q][i]]--; for (int p=q+1;p<=n;++p) { s[p]=-1; for (int i=0;i<g[p].size();++i) s[g[p][i]]--; vector <int> _s=s; ww=0; for (int i=1;i<=n;++i) odp[i]=1; for (int j=1;j<=n;++j) if (s[j]==0) DFS(g,_s,odp,j); for (int i=1;i<=n;++i) if (s[i]!=-1&&odp[i]>ww) ww=odp[i]; if (ww<wynik) wynik=ww; s[p]=stop_w[p]; for (int i=0;i<g[p].size();++i) s[g[p][i]]++; } s[q]=stop_w[q]; for (int i=0;i<g[q].size();++i) s[g[q][i]]++; } s[v]=stop_w[v]; for (int i=0;i<g[v].size();++i) s[g[v][i]]++; } cout << wynik; return 0; } vector <int> s=stop_w; wynik=1000; for (int v=1;v<=n;++v) { s[v]=-1; for (int i=0;i<g[v].size();++i) s[g[v][i]]--; for (int d=v+1;d<=n;++d) { s[d]=-1; for (int i=0;i<g[d].size();++i) s[g[d][i]]--; for (int q=d+1;q<=n;++q) { s[q]=-1; for (int i=0;i<g[q].size();++i) s[g[q][i]]--; for (int p=q+1;p<=n;++p) { s[p]=-1; for (int i=0;i<g[p].size();++i) s[g[p][i]]--; vector <int> _s=s; ww=0; for (int i=1;i<=n;++i) odp[i]=1; for (int j=1;j<=n;++j) if (s[j]==0) DFS(g,_s,odp,j); for (int i=1;i<=n;++i) if (s[i]!=-1&&odp[i]>ww) ww=odp[i]; if (ww<wynik) wynik=ww; s[p]=stop_w[p]; for (int i=0;i<g[p].size();++i) s[g[p][i]]++; } s[q]=stop_w[q]; for (int i=0;i<g[q].size();++i) s[g[q][i]]++; } s[d]=stop_w[d]; for (int i=0;i<g[d].size();++i) s[g[d][i]]++; } s[v]=stop_w[v]; for (int i=0;i<g[v].size();++i) s[g[v][i]]++; } cout << wynik; return 0; } |