# include <cstdio> # include <algorithm> # include <string> const short int MAX_N = 302; const short int MAX_M = 402; struct node { short int in_total = 0; short int out_total = 0; short int in[ MAX_N ]; short int out[ MAX_N ]; }; inline short int max( short int a, short int b ) { return ( a > b ) ? a : b; } inline short int min( short int a, short int b ) { return ( a < b ) ? a : b; } short int evaluate_graph( node graph[ ], short int n, std::string removed ) { short int longest_path = 0; short int longest_in[ MAX_N ]; for ( short int i = 1; i <= n; i ++ ) { longest_in[ i ] = 1; } node * current_node; for ( short int node_number = 1; node_number <= n; node_number ++ ) { if ( removed[ node_number - 1] ) { continue; } current_node = & graph[ node_number ]; for ( short int in_index = 0; in_index < current_node->in_total; in_index ++ ) { short int neighbour_index = current_node->in[ in_index ]; if ( removed[ neighbour_index - 1] ) { continue; } short int path_len = longest_in[ neighbour_index ] + 1; longest_in[ node_number ] = max( longest_in[ node_number ], path_len ); } longest_path = max( longest_in[ node_number ], longest_path ); } return longest_path; } int main() { short int n, m, k; node graph[ MAX_N ]; scanf( "%hd %hd %hd", & n, & m, & k ); for ( short int i = 0; i < m; i ++ ) { short int x, y; scanf( "%hd %hd", & x, & y ); graph[ x ].out[ graph[ x ].out_total ] = y; graph[ x ].out_total ++; graph[ y ].in[ graph[ y ].in_total ] = x; graph[ y ].in_total ++; } short int result = MAX_N; std::string removed_bitmask( k, 1 ); removed_bitmask.resize( n, 0 ); do { short int perm_result = evaluate_graph( graph, n, removed_bitmask ); result = min( perm_result, result ); } while ( std::prev_permutation( removed_bitmask.begin(), removed_bitmask.end() ) ); printf( "%hd", result ); 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 | # include <cstdio> # include <algorithm> # include <string> const short int MAX_N = 302; const short int MAX_M = 402; struct node { short int in_total = 0; short int out_total = 0; short int in[ MAX_N ]; short int out[ MAX_N ]; }; inline short int max( short int a, short int b ) { return ( a > b ) ? a : b; } inline short int min( short int a, short int b ) { return ( a < b ) ? a : b; } short int evaluate_graph( node graph[ ], short int n, std::string removed ) { short int longest_path = 0; short int longest_in[ MAX_N ]; for ( short int i = 1; i <= n; i ++ ) { longest_in[ i ] = 1; } node * current_node; for ( short int node_number = 1; node_number <= n; node_number ++ ) { if ( removed[ node_number - 1] ) { continue; } current_node = & graph[ node_number ]; for ( short int in_index = 0; in_index < current_node->in_total; in_index ++ ) { short int neighbour_index = current_node->in[ in_index ]; if ( removed[ neighbour_index - 1] ) { continue; } short int path_len = longest_in[ neighbour_index ] + 1; longest_in[ node_number ] = max( longest_in[ node_number ], path_len ); } longest_path = max( longest_in[ node_number ], longest_path ); } return longest_path; } int main() { short int n, m, k; node graph[ MAX_N ]; scanf( "%hd %hd %hd", & n, & m, & k ); for ( short int i = 0; i < m; i ++ ) { short int x, y; scanf( "%hd %hd", & x, & y ); graph[ x ].out[ graph[ x ].out_total ] = y; graph[ x ].out_total ++; graph[ y ].in[ graph[ y ].in_total ] = x; graph[ y ].in_total ++; } short int result = MAX_N; std::string removed_bitmask( k, 1 ); removed_bitmask.resize( n, 0 ); do { short int perm_result = evaluate_graph( graph, n, removed_bitmask ); result = min( perm_result, result ); } while ( std::prev_permutation( removed_bitmask.begin(), removed_bitmask.end() ) ); printf( "%hd", result ); return 0; } |