学步园

     题目大意：有一个序列，题目用n个整数组合 [ai,bi,ci]来描述它，[ai，bi，ci]表示在该序列中处于[ai，bi]这个区间的整数至少有ci个。如果存在这样的序列，请求出满足题目要求的最短的序列长度是多少。如果不存在则输出 -1。

     题目分析：显然差分约束+spfa、其实这题我理解也不怎么深……不晓得差分约束怎么会和spfa结合起来。

     代码：

#include<cstdio><br /> #include<cstring><br /> #include<queue><br /> #include<vector><br /> #include<algorithm><br /> using namespace std;</p> <p>#define init(a,what) memset(a,what,sizeof(a))<br /> #define read freopen("zx.in","r",stdin)<br /> #define write freopen("zx.out","w",stdout)<br /> const int INF=0x3f3f3f3f;<br /> const int MAXN=50000+10;</p> <p>typedef struct<br /> {<br /> int num,p;<br /> }ZX;<br /> ZX zx;<br /> vector<ZX>map[MAXN];<br /> int nnum,minn,maxn,dist[MAXN];<br /> bool vis[MAXN];</p> <p>void spfa()<br /> {<br /> queue<int>q;<br /> init(vis,false);<br /> for(int i=minn;i<=maxn;i++) dist[i]=(i==minn ? 0 : -INF);<br /> vis[minn]=true;<br /> q.push(minn);<br /> while(!q.empty())<br /> {<br /> int xx=q.front();<br /> q.pop();<br /> vis[xx]=false;<br /> int curlen=map[xx].size();<br /> for(int i=0;i<curlen;i++)<br /> {<br /> if(dist[map[xx][i].p]<dist[xx]+map[xx][i].num)<br /> {<br /> dist[map[xx][i].p]=dist[xx]+map[xx][i].num;<br /> if(!vis[map[xx][i].p])<br /> {<br /> vis[map[xx][i].p]=true; q.push(map[xx][i].p);<br /> }<br /> }<br /> }<br /> }<br /> }</p> <p>int main()<br /> {<br /> read, write;<br /> int a,b,c;<br /> while(scanf("%d",&nnum)!=EOF)<br /> {<br /> minn=INF, maxn=-1;<br /> for(int i=1;i<=nnum;i++)<br /> {<br /> scanf("%d%d%d",&a,&b,&c);<br /> if(a<minn) minn=a;<br /> if(b+1>maxn) maxn=b+1;<br /> zx.num=c, zx.p=b+1;<br /> map[a].push_back(zx);<br /> }<br /> for(int i=minn;i<=maxn;i++)<br /> {<br /> zx.num=0, zx.p=i+1;<br /> map[i].push_back(zx);<br /> zx.num=-1, zx.p=i;<br /> map[i+1].push_back(zx);<br /> }<br /> spfa();<br /> printf("%d/n",dist[b]);<br /> }<br /> return 0;<br /> }<br />