http://poj.org/problem id=1201
题目大意：
有一个序列，题目用n个整数组合 [ai，bi，ci]来描述它，[ai，bi，ci]表示在该序列中处于[ai，bi]这个区间的整数至少有ci个。如果存在这样的序列，请求出满足题目要求的最短的序列长度是多少。
思路：
设s[i]为从1~i的整数个数。
这样对于区间[ a , b]显然有 S[b] - S[a-1] >=c[i] （为什么是a-1 因为闭区间a也要选上呀）
然后还有
0<= S[B]-S[B-1] <=1 （整数的话最多比前一个大一，好吧，我大二- -|||我不二啊！！）
变形得：
S[B]-S[B-1] >=0
S[B-1]-S[B]>=-1
然后图就可以建立出来啦~~~~
老样子，我也加了一个点连接到所有的点（为什么？见我上一篇http://blog.csdn.net/murmured/article/details/18780557）
#include#include #include using namespace std; const int MAXN=50000+10; const int MAXM=500000; const int INF=-100000000; struct edge { int to; int val; int next; }e[MAXM]; int head[MAXN],len,n,m,c,start,dis[MAXN]; void add(int from,int to,int val) { e[len].to=to; e[len].val=val; e[len].next=head[from]; head[from]=len++; } bool vis[MAXN]; void spfa() { for(int i=start;i<=n;i++) { dis[i]=INF; vis[i]=0; } queue q; dis[0]=0; vis[0]=true; q.push(0); while(!q.empty()) { int cur=q.front(); q.pop(); vis[cur]=false; for(int i=head[cur];i!=-1;i=e[i].next) { int id=e[i].to; if(dis[cur] + e[i].val > dis[id]) { dis[id]=dis[cur]+e[i].val; if(!vis[id]) { vis[id]=true; q.push(id); } } } } } int main() { while(~scanf("%d",&m)) { len=0; memset(head,-1,sizeof(head)); n=0; start=9999999; for(int i=1;i<=m;i++) { int from,to,val; scanf("%d%d%d",&from,&to,&val); add(from-1,to,val); if(to >n) n=to; if(start > from) start=from; } for(int i=start;i<=n;i++) { add(0,i,0); add(i,i-1,-1); add(i-1,i,0); } spfa(); printf("%d\n",dis[n]); } return 0; }