传送门:【HDU】1534 Schedule Problem
题目分析:比较简单的差分约束。
每个任务X设一个开始时间Xs,结束时间Xe。
如果任务X需要时间t完成。设不等式:Xe - Xs >= t , Xs - Xe >= -t
SAS X Y:Xs - Ys >= 0
SAF X Y:Xs - Ye >= 0
FAS X Y:Xe - Ys >= 0
FAF X Y:Xe - Ye >= 0
最后将形如Y - X >= d的不等式建边( X , Y , d ),跑一遍spfa最长路,如果无正权环则有解,d[ i ](1 <= i <= n)则为第i个任务的满足条件的最小开始时间。如果有正权环出现则无解。
题目坑的不行啊,一个数据范围都没有给。
代码如下:
#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 ) #define CPY( a , x ) memcpy ( a , x , sizeof a ) const int MAXN = 400 ; const int MAXE = 1000000 ; const int INF = 0x3f3f3f3f ; struct Edge { int v , c ; Edge* next ; } E[MAXE] , *H[MAXN] , *cur ; int d[MAXN] ; int Q[MAXN] , head , tail ; bool inq[MAXN] ; int in[MAXN] ; int n ; void init () { cur = E ; CLR ( H , 0 ) ; } void addedge ( int u , int v , int c ) { cur -> v = v ; cur -> c = c ; cur -> next = H[u] ; H[u] = cur ++ ; } bool spfa () { CLR ( in , 0 ) ; CLR ( inq , 0 ) ; FOR ( i , 0 , n << 1 ) d[i] = -INF ; head = tail = 0 ; d[0] = 0 ; Q[tail ++] = 0 ; 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] + e -> c ) { d[v] = d[u] + e -> c ; if ( !inq[v] ) { if ( ++ in[v] > 2 * n + 1 ) return 0 ; inq[v] = 1 ; Q[tail ++] = v ; if ( tail == MAXN ) tail = 0 ; } } } } return 1 ; } void solve () { int x , y ; char s[5] ; init () ; FOR ( i , 1 , n ) addedge ( 0 , i , 0 ) ; FOR ( i , 1 , n ) { scanf ( "%d" , &x ) ; addedge ( i , i + n , x ) ; addedge ( i + n , i , -x ) ; } while ( ~scanf ( "%s" , s ) && s[0] != '#' ) { scanf ( "%d%d" , &x , &y ) ; if ( s[0] == 'S' ) { if ( s[2] == 'S' ) addedge ( y , x , 0 ) ; else addedge ( y + n , x , 0 ) ; } else { if ( s[2] == 'S' ) addedge ( y , x + n , 0 ) ; else addedge ( y + n , x + n , 0 ) ; } } if ( spfa () ) FOR ( i , 1 , n ) printf ( "%d %d\n" , i , d[i] ) ; else printf ( "impossible\n" ) ; } int main () { int cas = 0 ; while ( ~scanf ( "%d" , &n ) && n ) { if ( cas ) printf ( "\n" ) ; printf ( "Case %d:\n" , ++ cas ) ; solve () ; } return 0 ; }