一道很蛋疼的题... 虽然很明显的差分约束，但是我就是那么错了。N久N久啊~~到现在我还是不知道为甚么！！！虽然很明显的是差分约束题，而且网上的资料乱七八糟的.... 看到了两条有用的结论：
1.求最大值，采用最短路径求法。
2.求最小值，采用最长路径求法。
但是！为什么啊？为什么？？看来我还是对图论理解不深啊....
稍后继续想想这题吧....
#include<iostream>
#include<queue>
#define INF 0x7F7F7F7F
#define MAXN 50005
using namespace std;struct Node
{int v;int price;Node *next;
}Edge[MAXN<<2],*ptr[MAXN];int N;
int dist[MAXN];
int edgeNum;
int maxV,minV;void addEdge( int u,int v,int val )
{Node *p=&Edge[edgeNum++];p->v=v;p->price=val;p->next=ptr[u];ptr[u]=p;
}bool spfa()
{bool used[MAXN];int cnt[MAXN];memset( used,0,sizeof(used) );memset( cnt,0,sizeof(cnt) );memset( dist,0xFF,sizeof(dist) );queue<int>myQueue;while( !myQueue.empty() ) myQueue.pop();dist[minV]=0;myQueue.push(minV);while( !myQueue.empty() ){int u=myQueue.front();myQueue.pop();Node *p=ptr[u];used[u]=false;while( p ){if( dist[p->v]<dist[u]+p->price ){dist[p->v]=dist[u]+p->price;if( !used[p->v] ){used[p->v]=true;myQueue.push(p->v);if( ++cnt[p->v]>maxV )return false;}}p=p->next;}}return true;
}int main()
{while( scanf( "%d",&N )!=EOF ){int i,j;int u,v,p;int edgeNum=0;for( i=0;i<MAXN;i++ )ptr[i]=NULL;maxV=0;minV=INF;for( i=1;i<=N;i++ ){scanf( "%d %d %d",&u,&v,&p );if( v+1>maxV ) maxV=v+1;if( u<minV ) minV=u;addEdge(u,v+1,p);}for( i=minV;i<=maxV;i++ ){addEdge( i,i+1,0 );addEdge( i+1,i,-1 );}spfa();printf( "%d\n",dist[maxV] );}return 0;
}