#include <algorithm> #include <cstdio> #include <vector> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define FORD(i,a,b) for(int i=(b)-1;i>=(a);--i) #define REP(i,n) FOR(i,0,n) #define REPD(i,n) FORD(i,0,n) #define VAR(v,w) __typeof(w) v=(w) #define FORE(it,c) for(VAR(it,(c).begin());it!=(c).end();++it) #define PB push_back #define INT(x) int x; scanf("%d", &x) typedef vector<int> VI; bool p[300]; VI g[300]; int h[300]; int main() { INT(n); INT(m); INT(k); REP(x,m) { INT(a); INT(b); g[a - 1].PB(b - 1); } FOR(i,n-k,n) p[i] = 1; int res = n; do { int r = 0; REPD(i,n) { h[i] = 0; if (p[i]) continue; FORE(it,g[i]) h[i] = max(h[i], h[*it]); ++h[i]; r = max(r, h[i]); } res = min(res, r); } while (next_permutation(p, p + n)); printf("%d\n", res); }
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 | #include <algorithm> #include <cstdio> #include <vector> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define FORD(i,a,b) for(int i=(b)-1;i>=(a);--i) #define REP(i,n) FOR(i,0,n) #define REPD(i,n) FORD(i,0,n) #define VAR(v,w) __typeof(w) v=(w) #define FORE(it,c) for(VAR(it,(c).begin());it!=(c).end();++it) #define PB push_back #define INT(x) int x; scanf("%d", &x) typedef vector<int> VI; bool p[300]; VI g[300]; int h[300]; int main() { INT(n); INT(m); INT(k); REP(x,m) { INT(a); INT(b); g[a - 1].PB(b - 1); } FOR(i,n-k,n) p[i] = 1; int res = n; do { int r = 0; REPD(i,n) { h[i] = 0; if (p[i]) continue; FORE(it,g[i]) h[i] = max(h[i], h[*it]); ++h[i]; r = max(r, h[i]); } res = min(res, r); } while (next_permutation(p, p + n)); printf("%d\n", res); } |