题目分析:差分约束系统第一题。。。。
什么是差分约束系统,就是给你一组类似于xj-xi<=ci的不等式,让你求向量x的一组解(一般只让你求某个元素的值)。对于xj-xi<=ci这个不等式我们能得到什么有用的信息?没错!xj-xi<=ci ---> xj<=xi+ci ---> d[v]<=d[u]+Edge[u][v]!
瞬间和图论中的松弛的三角不等式对应起来了!这样我们只要对所有的xj-xi<=ci建边(xi,xj,ci),然后再设立一个源点,源点s到所有的边权为0,即xi-xs<=0,建边(xs,xi,0),从源点跑一遍单源最短路就能得到差分约束系统的一组解,但是要在图中无负环的前提下,因为如果存在负环则差分约束系统无解。为什么?假设存在x1-x2<=-3,x3-x1<=1,x2-x3<=-2,那么将这个不等式组相加后得到0<=-5,显然这是矛盾的,所以不等式组无解。
对于本题,由于bi-ai>=ci,所以我们可以得到一组不等式ai-bi<=-ci,并且由于x(i)-x(i-1)<=1,x(i-1)-x(i)<=0(x(i)-x(i-1)>=0),所以我们将这所有的关系用上述方法建边先。注意到本题要求的其实就是所有区间最小的最左端minv到所有区间最大的最右端maxv内符合条件的最少的c的个数,设d[i]为0~i内最少的c的个数,那么答案即d[maxv] - d[minv-1],我们可以直接令maxv为源点,那么答案就是-d[minv-1]。
代码如下:
#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 = 50005 ; const int MAXQ = 50005 ; const int MAXE = 1000000 ; const int INF = 0x3f3f3f3f ; struct Edge { int v , c ; Edge *next ; Edge () {} Edge ( int v , int c , Edge *next ) : v ( v ) , c ( c ) , next ( next ) {} } E[MAXE] , *H[MAXN] , *cntE ; int d[MAXN] ; bool inq[MAXN] ; int Q[MAXN] , head , tail ; int n ; void init () { cntE = E ; CLR ( H , 0 ) ; } void addedge ( int u , int v , int c ) { cntE -> v = v ; cntE -> c = c ; cntE -> next = H[u] ; H[u] = cntE ++ ; } void spfa ( int s ) { CLR ( inq , 0 ) ; CLR ( d , INF ) ; head = tail = 0 ; d[s] = 0 ; Q[tail ++] = s ; while ( head != tail ) { int u = Q[head ++] ; if ( head == MAXQ ) 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] ) { inq[v] = 1 ; Q[tail ++] = v ; if ( tail == MAXQ ) tail = 0 ; } } } } } void solve () { int u , v , c ; int minv = INF , maxv = 0 ; init () ; REP ( i , 0 , n ) { scanf ( "%d%d%d" , &u , &v , &c ) ; addedge ( v , u - 1 , -c ) ; minv = min ( minv , u ) ; maxv = max ( maxv , v ) ; } FOR ( i , minv , maxv ) { addedge ( i , i - 1 , 0 ) ; addedge ( i - 1 , i , 1 ) ; } spfa ( maxv ) ; printf ( "%d\n" , -d[minv - 1] ) ; } int main () { while ( ~scanf ( "%d" , &n ) ) solve () ; return 0 ; }