#include <bits/stdc++.h> using namespace std; const int N = 301; int n, m, k, out=N; int dist [N]; int from [N]; bool del [N]; vector <int> e [N]; vector <int> path [5]; void pleh (int k) { int w=0; for (int u=1; u<=n; u++) { dist[u]=1; from[u]=0; } for (int u=1; u<=n; u++) if (!del[u]) { for (int v : e[u]) if (dist[v]<dist[u]+1) { dist[v]=dist[u]+1; from[v]=u; } if (dist[u]>dist[w]) w=u; } if (k==0) { out=min(out,dist[w]); return; } path[k].clear(); path[k].push_back(w); for (w=from[w]; w!=0; w=from[w]) path[k].push_back(w); for (int v : path[k]) { del[v]=true; pleh(k-1); del[v]=false; } } int main () { scanf ("%d%d%d",&n,&m,&k); while (m--) { int a, b; scanf ("%d%d",&a,&b); e[a].push_back(b); } pleh(k); printf ("%d\n",out); 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 | #include <bits/stdc++.h> using namespace std; const int N = 301; int n, m, k, out=N; int dist [N]; int from [N]; bool del [N]; vector <int> e [N]; vector <int> path [5]; void pleh (int k) { int w=0; for (int u=1; u<=n; u++) { dist[u]=1; from[u]=0; } for (int u=1; u<=n; u++) if (!del[u]) { for (int v : e[u]) if (dist[v]<dist[u]+1) { dist[v]=dist[u]+1; from[v]=u; } if (dist[u]>dist[w]) w=u; } if (k==0) { out=min(out,dist[w]); return; } path[k].clear(); path[k].push_back(w); for (w=from[w]; w!=0; w=from[w]) path[k].push_back(w); for (int v : path[k]) { del[v]=true; pleh(k-1); del[v]=false; } } int main () { scanf ("%d%d%d",&n,&m,&k); while (m--) { int a, b; scanf ("%d%d",&a,&b); e[a].push_back(b); } pleh(k); printf ("%d\n",out); return 0; } |