POJ 1201 Intervals

题意：有n个区间[a,b]，每个区间有一个值c。找一个集合中的元素使得每个区间至少有c个元素在这个集合中，问最小的集合大小。

思路：设d[i+1]表示0到i有多少个数在这个集合中，显然对于每个区间，d[b+1]-d[a]>=c，才能符合题目的要求。但是这样并不能使得所有集合都联系起来。继续挖掘条件，根据d[]的定义可得，0<=d[i+1]-d[i]<=1。

由此可得三个不等式：

d[b+1]-d[a]>=c

d[i+1]-d[i]>=0

d[i]-d[i+1]>=-1

很明显这是一个差分约束系统，只不过求得是最长路。建好图后找到最小值到最大值的最长路就是答案。

 1 #include<stdio.h>
 2 #include<string.h>
 3 const int N=50000+111,M=200000,INF=0x3f3f3f3f;
 4 struct node{
 5     int v,w,next;
 6 }e[M];
 7 int head[N],p[N],d[N];
 8 int q[M<<2],l,r,js;
 9 void add(int u,int v,int w)
10 {
11     e[js].v=v,e[js].w=w;
12     e[js].next=head[u],head[u]=js++;
13 }
14 void spfa(int s,int t)
15 {
16     l=r=0;int u,v,w,i;
17     for(i=s;i<=t;i++)    d[i]=-INF; 
18     memset(p,0,sizeof(p));
19     q[++r]=s;d[s]=0;
20     while(l<r)
21     {
22         p[u=q[++l]]=0;
23         for(i=head[u];i!=-1;i=e[i].next)
24         {
25             v=e[i].v,w=e[i].w;
26             if(d[v]<d[u]+w)
27             {
28                 d[v]=d[u]+w;
29                 if(!p[v])
30                 {
31                     p[v]=1;
32                     q[++r]=v;
33                 }
34             }
35         }
36     }
37     printf("%d
",d[t]);
38 }
39 int main()
40 {
41     int n,u,v,w,i,ma,mi;
42     while(scanf("%d",&n)!=EOF)
43     {
44         memset(head,-1,sizeof(head));
45         js=ma=0;mi=INF;
46         while(n--)
47         {
48             scanf("%d%d%d",&u,&v,&w);
49             add(u,v+1,w);
50             if(u<mi)    mi=u;
51             if(v+1>ma)    ma=v+1;
52         }
53         for(i=mi;i<ma;i++)
54         {
55             add(i,i+1,0);
56             add(i+1,i,-1);
57         }
58         spfa(mi,ma);
59     }
60     return 0;
61 }