题意：
有一个集合Z，其元素都是整整数，但是数量未知。现有n个约束，形如 [a,b]=c 表示整数区间[a,b]中有c个元素在Z中出现。问集合Z最小可能含多少个元素？
思路：
对于所给的区间 cnt[b-a]>=k这可以保证了该区间内个数不少于k。但是由于两边都是闭区间，所以要变cnt[b-(a-1)]>=k，表示b到a之间的个数。也就是说，转成式子是b-(a-1)>=k，变换一下为(a-1)-b<=-k，就满足常见的式子b-a<=k啦，可以建边b指向(a-1)，权值为-k。
但是还有没有其他的约束条件呢？如果我们只是这样建图，那很多个点都不会有联系的啊，比如[3,7]>=2和 [5,9]>=4，建边为2->7和4>9，完全不搭边啊！肯定还有其他联系，相邻的两个数字之间是否可以有边？可以的，至少可以满足a-(a-1)>=0吧？表示a只能被选与不被选。还有呢？每个点最多只能被选一次吧？则有a-(a-1)<=1。
综合3条式子，可以变形得到：
（1）(a-1)-b<=-k
（2）(a-1)-a<=0
（3）a-(a-1)<=1
都满足了常见的式子。那么可以建边了。这下每两个相邻数字就起码有两条边。注意：求的值是最小的，所以标准形式用<=号。
我们要求的是什么？满足要求的，整个区间所挑的最小个数。从最大数字出发，进行求最短路后，最小的数的那个点通常就会得到一个负权路径和啦,cost[最小]=负值。而cost[最小]取相反数就是答案了。记得开始前要将cost[起点]置为0。大概思路是这样，但是区间是[0,50000]，所以0-1时还会出现负数下标，可以将整个区间右移一位变成[1,50001]。
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <map>
#include <iostream>
#include <deque>
#include <vector>
#define INF 0x7f7f7f7f
#define pii pair<int,int>
#define LL unsigned long long
using namespace std;
const int N=;
struct node
{
int from,to,cost;
node(){};
node(int from,int to,int cost):from(from),to(to),cost(cost){};
}edge[N*];
vector<int> vect[N];
int edge_cnt; void add_node(int from,int to,int cost)
{
edge[edge_cnt]=node(from,to,cost);
vect[from].push_back(edge_cnt++);
} bool inq[N];
int cost[N];
int spfa(int small,int big)
{
memset(inq, , sizeof(inq));
memset(cost, 0x7f, sizeof(cost));
cost[big]=;
deque<int> que(,big); while(!que.empty())
{
int x=que.front();que.pop_front();
inq[x]=; for(int i=; i<vect[x].size(); i++)
{
node e=edge[vect[x][i]];
if(cost[e.to]>cost[x]+e.cost)
{
cost[e.to]=cost[x]+e.cost;
if(!inq[e.to])
{
inq[e.to]=;
if(!que.empty() && cost[e.to]<cost[que.front()]) que.push_front(e.to);
else que.push_back(e.to);
}
}
}
}
return -cost[small];
} int main()
{
//freopen("input.txt", "r", stdin);
int n, m, a, b, c;
while(~scanf("%d",&n))
{
edge_cnt=;
memset(edge,,sizeof(edge));
for(int i=; i<N; i++) vect[i].clear();
int small=INF, big=; for(int i=; i<n; i++)
{
scanf("%d%d%d",&a,&b,&c);
add_node(b+,a,-c); //右移了1位 small=min(small, a+);
big=max(big, b+);
}
//每两个点之间的
for(int i=small; i<=big; i++)
{
add_node(i-, i, );
add_node(i, i-, );
}
cout<<spfa(small-, big)<<endl;
}
return ;
}
AC代码