传送门:【HDU】1317 XYZZY
题目分析:首先我们可以用spfa判最长路上是否有正权环,但是有正权环却不等价于能到达终点。这是我们还需要判断是否能从正权环中走到终点,这个可以用传递闭包搞定。如果没有正权环就看是否能从起点到终点就好了。
代码如下:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std ; #define REP( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i ) #define FOR( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i ) #define REV( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i ) #define CLR( a , x ) memset ( a , x , sizeof a ) const int MAXN = 105 ; const int MAXE = 23333 ; const int INF = 0x3f3f3f3f ; struct Edge { int v ; //int c ; Edge* next ; } E[MAXE] , *H[MAXN] , *cur ; int d[MAXN] ; int Q[MAXN] , head , tail ; bool inq[MAXN] ; int in[MAXN] ; int n ; int val[MAXN] ; bool G[MAXN][MAXN] ; void init () { cur = E ; CLR ( H , 0 ) ; } void addedge ( int u , int v , int c = 0 ) { cur -> v = v ; //cur -> c = c ; cur -> next = H[u] ; H[u] = cur ++ ; } bool spfa () { CLR ( in , 0 ) ; CLR ( inq , 0 ) ; CLR ( d , -INF ) ; head = tail = 0 ; Q[tail ++] = 1 ; d[1] = 100 ; while ( head != tail ) { int u = Q[head ++] ; if ( head == MAXN ) head = 0 ; inq[u] = 0 ; for ( Edge* e = H[u] ; e ; e = e -> next ) { int v = e -> v ; if ( d[v] < d[u] + val[v] && d[u] + val[v] > 0 ) { d[v] = d[u] + val[v] ; if ( !inq[v] ) { if ( ++ in[v] > n ) return G[v][n] ; inq[v] = 1 ; Q[tail ++] = v ; if ( tail == MAXN ) tail = 0 ; } } } } return d[n] > 0 ; } void scanf ( int& x , char c = 0 ) { while ( ( c = getchar () ) < '0' || c > '9' ) ; x = c - '0' ; while ( ( c = getchar () ) >= '0' && c <= '9' ) x = x * 10 + c - '0' ; } void solve () { int m , v ; init () ; CLR ( G , 0 ) ; FOR ( i , 1 , n ) { scanf ( "%d" , &val[i] ) ; scanf ( "%d" , &m ) ; while ( m -- ) { scanf ( "%d" , &v ) ; addedge ( i , v ) ; G[i][v] = 1 ; } } FOR ( k , 1 , n ) FOR ( i , 1 , n ) FOR ( j , 1 , n ) G[i][j] |= G[i][k] & G[k][j] ; if ( spfa () ) printf ( "winnable\n" ) ; else printf ( "hopeless\n" ) ; } int main () { while ( ~scanf ( "%d" , &n ) && ~n ) solve () ; return 0 ; }