POJ1201 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

Sample Output

Source

Southwestern Europe 2002

正解：SPFA+差分约束系统

解题报告：

　　大致题意是给定一些要求，比如说，1到7之间至少有5个数，然后条件需要全部满足，问

　　这几天刷了几道差分约束系统+SPFA的题目，现在向总给的题目清单里面就只剩下一道半平面交没做了。夏令营回来有时间再切了吧。

　　这道题也没什么好说的，只不过是根据大于号建图，跑最长路就可以了。

　　唯一要注意的是因为是前缀和建图，需要把这个序列依次连边，比如说1连2连3这么一直连接下去。

 1 //It is made by jump~
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <algorithm>
 8 #include <ctime>
 9 #include <vector>
10 #include <queue>
11 #include <map>
12 #ifdef WIN32   
13 #define OT "%I64d"
14 #else
15 #define OT "%lld"
16 #endif
17 using namespace std;
18 typedef long long LL;
19 const int inf = (1<<30);
20 const int MAXN = 500011;
21 const int MAXM = 500011;
22 int n;
23 int first[MAXN],next[MAXM],to[MAXM],w[MAXM];
24 int dis[MAXN];
25 bool pd[MAXN];
26 int ecnt;
27 int Min,Max;
28 int ans;
29 queue<int>Q;
30 
31 inline int getint()
32 {
33        int w=0,q=0;
34        char c=getchar();
35        while((c<'0' || c>'9') && c!='-') c=getchar();
36        if (c=='-')  q=1, c=getchar();
37        while (c>='0' && c<='9') w=w*10+c-'0', c=getchar();
38        return q ? -w : w;
39 }
40 
41 inline void Init(){
42     ecnt=0; memset(first,0,sizeof(first));
43     Max=0; Min=inf;
44     while(!Q.empty()) Q.pop();
45     ans=0;
46 }
47 
48 inline void link(int x,int y,int z){
49     next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y; w[ecnt]=z;
50 }
51 
52 inline void spfa(){
53     for(int i=0;i<=n;i++) dis[i]=-inf;
54     Q.push(Min); pd[Min]=1; dis[Min]=0;
55     while(!Q.empty()) {
56     int u=Q.front(); Q.pop(); pd[u]=0;
57     for(int i=first[u];i;i=next[i]) { //最长路
58         int v=to[i];
59         if(dis[v]<dis[u]+w[i]) {
60         dis[v]=dis[u]+w[i];
61         if(!pd[v]){
62             Q.push(v); pd[v]=1;
63         }
64         }
65     }
66     }
67     ans=dis[Max];
68 }
69 
70 inline void solve(){
71     while(scanf("%d",&n)!=EOF){
72         Init();
73     int x,y,z;
74     for(int i=1;i<=n;i++) {
75         x=getint()-1;y=getint();z=getint();
76         link(x,y,z);
77         Min=min(Min,x); Max=max(Max,y);
78     }
79     for(int i=Min;i<Max;i++){//以前缀和为结点
80         link(i+1,i,-1); link(i,i+1,0);//要使所有点满足s[i+1]-s[i] <= 1 &&  s[i]-s[i+1] <= 0
81     }
82     spfa();
83     printf("%d",ans);
84     }
85 }
86 
87 int main()
88 {
89   solve();
90   return 0;
91 }