http://poj.org/problem?id=1201
题意：给定n个整数闭区间[a,b]和n个整数c，求一个最小的整数集合Z，满足Z里边的数中范围在闭区间[a,b]的个数不小于c个。
思路：根据题目描述，可建模成一个差分约束系统。
设S[i]表示小于等于i的整数的个数，R表示最大的右端点值,L表示最小的左端点值：
则 S[b] - S[a-1] >= c;
转化成：S[a-1] - S[b] <= -c;...... (1)
S[i] - S[i-1] <= 1; ........ (2)
S[i] -S[i-1] >= 0;
转化成：S[i-1] - S[i] <= 0;.......... (3)
(1)(2)(3)即为三个约束条件。最终要求的就是S[R] - S[L-1] >= M,即 S[L-1] - S[R] <= -M;
#include <stdio.h>
#include <string.h>
const int N=;
const int INF=<<;
struct node
{
int u,v,w;
} edge[N];
int dis[N];
int n,cnt,l,r;//l表示所有左端点的最小值，r表示所有右端点的最大值
void add(int u,int v,int w)
{
edge[cnt].u = u;
edge[cnt].v = v;
edge[cnt++].w = w;
}
bool bellman_ford()
{
memset(dis,,sizeof(dis));
int flag = ;//只要某次循环过程中，没能改变源点到各顶点的最短距离，则可以提前结束循环
while(flag)
{
flag = ;
for (int i = ; i < n; i++)
{
int u = edge[i].u;
int v = edge[i].v;
if (dis[v] > dis[u]+edge[i].w)
{
dis[v] = dis[u]+edge[i].w;
flag = ;
}
}
for (int i = l; i <= r; i++)//根据约束条件s[i] <= s[i-1]+1,进一步修改s[i];
{
if (dis[i-]+ < dis[i])
{
dis[i] = dis[i-]+;
flag = ;
}
}
for (int i = r; i >= l; i--)//根据约束条件S[i] >= s[i-1],进一步修改s[i-1];
{
if (dis[i] < dis[i-])
{
dis[i-] = dis[i];
flag = ;
} }
}
return true;
}
int main()
{
int a,b,c;
while(~scanf("%d",&n))
{
cnt = ,r = ,l = INF;
for (int i = ; i < n; i++)
{
scanf("%d %d %d",&a,&b,&c);
add(b,a-,-c);//构造边
if (l > a)
l = a;//左端点的最小值
if (r < b)
r = b;//右端点的最小值
}
bellman_ford();
printf("%d\n",dis[r]-dis[l-]);
}
return ;
}