Intervals Description
You are given n closed, integer intervals [ai, bi] and n integers c1, …, cn. Write a program that: reads the number of intervals, their end points and integers c1, …, cn from the standard input, computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i=1,2,…,n, writes the answer to the standard output. Input
The first line of the input contains an integer n (1 <= n <= 50000) – the number of intervals. The following n lines describe the intervals. The (i+1)-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50000 and 1 <= ci <= bi - ai+1. Output
The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i=1,2,…,n. Sample Input
5 3 7 3 8 10 3 6 8 1 1 3 1 10 11 1 Sample Output
6 Source
Southwestern Europe 2002
关于差分约束系统的详细解释与入门，还有各个最短路算法的详解与优化大家可以看看这篇博客。写的非常的好！！！
夜深人静写算法： http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html
题意： 给定n（n <= 50000）个整点闭区间和这个区间中至少有多少整点需要被选中，每个区间的范围为[ai, bi]，并且至少有ci个点需要被选中，其中0 <= ai <= bi <= 50000，问[0, 50000]至少需要有多少点被选中。
分析： 这是一个典型的差分约束系统的题目。
例如3 6 2 表示[3, 6]这个区间至少需要选择2个点，可以是3,4也可以是4,6（总情况有 C(4, 2)种 ）。
这类问题就没有线性约束那么明显，需要将问题进行一下转化，考虑到最后需要求的是一个完整区间内至少有多少点被选中，试着用d[i]表示[0, i]这个区间至少有多少点能被选中，根据定义，可以抽象出 d[-1] = 0，对于每个区间描述，可以表示成d[ bi ] - d[ ai - 1 ] >= ci，而我们的目标要求的是 d[ 50000 ] - d[ -1 ] >= T 这个不等式中的T，将所有区间描述转化成图后求-1到50000的最长路。 这里忽略了一些要素，因为d[i]描述了一个求和函数，所以对于d[i]和d[i-1]其实是有自身限制的，考虑到每个点有选和不选两种状态，所以d[i]和d[i-1]需要满足以下不等式： 0 <= d[i] - d[i-1] <= 1 （即第i个数选还是不选） 这样一来，还需要加入 50000*2 = 100000 条边，由于边数和点数都是万级别的，所以不能采用单纯的Bellman-Ford ，需要利用SPFA进行优化，由于-1不能映射到小标，所以可以将所有点都向x轴正方向偏移1个单位（即所有数+1）。
AC代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> using namespace std; const int INF = 0xffffff; struct Edge { int u,v,w,next; Edge(){} Edge(int u_,int v_,int w_) { u = u_; v = v_; w = w_; } }edges[200000]; int head[50010]; int d[50010]; int e = 0,maxnum = 0; void addedge(int u,int v,int w) { edges[e] = Edge(u,v,w); edges[e].next = head[u]; head[u] = e++; } int inq[50010]; void spfa() { queue<int> q; while(!q.empty()) q.pop(); for(int i=0;i<=maxnum;i++) d[i] = -INF; d[0] = 0; memset(inq,0,sizeof(inq)); q.push(0); inq[0] = 1; while(!q.empty()) { int u = q.front(); q.pop(); inq[u]--; for(int i=head[u];i!=-1;i=edges[i].next) { int v = edges[i].v; if(d[v] < d[u] + edges[i].w) { d[v] = d[u] + edges[i].w; if(!inq[v]) { inq[v]++; q.push(v); } } } } } int main() { int n,u,v,w; scanf("%d",&n); memset(head,-1,sizeof(head)); maxnum = 0; e = 0; while(n--) { scanf("%d%d%d",&u,&v,&w); if(v+1 > maxnum) maxnum = v+1;//整体+1了，所以是v+1 addedge(u,v+1,w); //整体+1 } //0 <= d[i] - d[i-1] <= 1（即第i个数选还是不选） for(int i=0;i<=maxnum;i++) { addedge(i,i+1,0); addedge(i+1,i,-1); } spfa(); printf("%d\n",d[maxnum]); return 0; }