Intervals(差分约束系统)

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;

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int N=50005;
 4 const int INF=1<<28;
 5 struct node
 6 {
 7     int u,v,w;
 8 } edge[N];
 9 int dis[N];
10 int n,cnt,l,r;//l表示所有左端点的最小值，r表示所有右端点的最大值
11 void add(int u,int v,int w)
12 {
13     edge[cnt].u = u;
14     edge[cnt].v = v;
15     edge[cnt++].w = w;
16 }
17 bool bellman_ford()
18 {
19     memset(dis,0,sizeof(dis));
20     int flag = 1;//只要某次循环过程中，没能改变源点到各顶点的最短距离，则可以提前结束循环
21     while(flag)
22     {
23         flag = 0;
24         for (int i = 0; i < n; i++)
25         {
26             int u = edge[i].u;
27             int v = edge[i].v;
28             if (dis[v] > dis[u]+edge[i].w)
29             {
30                 dis[v] = dis[u]+edge[i].w;
31                 flag = 1;
32             }
33         }
34         for (int i = l; i <= r; i++)//根据约束条件s[i] <= s[i-1]+1,进一步修改s[i];
35         {
36             if (dis[i-1]+1 < dis[i])
37             {
38                 dis[i] = dis[i-1]+1;
39                 flag = 1;
40             }
41         }
42         for (int i = r; i >= l; i--)//根据约束条件S[i] >= s[i-1],进一步修改s[i-1];
43         {
44             if (dis[i] < dis[i-1])
45             {
46                 dis[i-1] = dis[i];
47                 flag = 1;
48             }
49 
50         }
51     }
52     return true;
53 }
54 int main()
55 {
56     int a,b,c;
57     while(~scanf("%d",&n))
58     {
59         cnt = 0,r = 0,l = INF;
60         for (int i = 0; i < n; i++)
61         {
62             scanf("%d %d %d",&a,&b,&c);
63             add(b,a-1,-c);//构造边
64             if (l > a)
65                 l = a;//左端点的最小值
66             if (r < b)
67                 r = b;//右端点的最小值
68         }
69         bellman_ford();
70         printf("%d
",dis[r]-dis[l-1]);
71     }
72     return 0;
73 }

View Code