题目大意如此： 现在有一个序列，我们用n个形如,ai,bi,ci的式子去描述它，表示序列中必须至少有大于等于ai并且小于等于bi的整数有ci个。要求输出序列长度最小为多少。 n的范围为50000，0 < a < b < 50000。 这个题我们一看就知道是差分约束（雾）。 我们令s[i]表示0到i的整数有多少个。 所以我们可以清楚地写出下列式子： s[b]-s[a-1]>=c s[i]-s[i-1]<=1（i取任意） s[i]-s[i-1]>=0（i取任意） 然后我们知道在做最短路的时候（只会spfa的我- -） 有一个三角式子dis[v] <= dis[u]+w(u,v) 我们变一下dis[v]-dis[u] <= w(u,v)是不是很像上面那个。 我们根据这样建边，也就是b到a-1建一条权值为-c的边。 i-1到i建一条权值为1的边。i到i-1建一条权值为0的边。 然后我们弄一个虚拟点s向每个点建一条权值为0的边。 这样以虚拟点s为源点跑spfa，那么就可以得到答案啦。 是不是特别简单。 当然这道题说明了一定有解，不然一定注意要判断是否存在负环，如果有说明无解。 代码如下：
#include<cstdio> #include<cstring> #include<queue> #include<algorithm> #define N 50010 #define inf 0x3f3f3f3f using namespace std; int n,num,head[N]; struct Edge{ int v,next,w; }; Edge e[10*N]; void adde(int i,int j,int w){ e[++num].v=j; e[num].next=head[i]; e[num].w=w; head[i]=num; } int vis[N],dis[N],s; void spfa(){ memset(dis,63,sizeof(dis)); queue<int>q; q.push(s); vis[s]=1; dis[s]=0; while(!q.empty()){ int u=q.front();q.pop();vis[u]=0; for(int i=head[u];i;i=e[i].next){ int v=e[i].v; if(dis[v]>dis[u]+e[i].w){ dis[v]=dis[u]+e[i].w; if(!vis[v]){ vis[v]=1; q.push(v); } } } } } int a,b,c; int main(){ s=N-2; scanf("%d",&n); int st=inf,ed=0; for(int i=1;i<=n;i++){ scanf("%d%d%d",&a,&b,&c); adde(b,a-1,-c); st=min(st,a); ed=max(ed,b); } for(int i=st;i<=ed;i++){ adde(i,i-1,0); adde(i-1,i,1); adde(s,i,0); } spfa(); // for(int i=st;i<=ed;i++)//这里可以输出具体方案 // if(dis[i]-dis[i-1]==1)printf("%d ",i); printf("%d\n",dis[ed]-dis[st-1]);//注意是st-1 return 0; }