【POJ1201】Intervals

                                                           Intervals

Time Limit: 2000MS	Memory Limit: 65536K
Total Submissions: 29689	Accepted: 11462

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
      

解析：

       设s[ k ]表示 0~k 之间最少选出多少个证书。有s[ bi ] - s[a[i] - 1] >= ci。这明显是差分约束系统。

       不过我们还需要增加一些条件使得解有意义：

       1.s[ k ] - s[ k - 1] >= 0。0~k 之间选出的数肯定不比 0~k - 1 少。

       2.s[ k ] - s[k - 1] <= 1。每个数只能选一次，可变形为s[k - 1] - s[ k ] >= -1。

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <queue>
using namespace std;

const int Max=50010;
int n,m,size,s,t;
int first[Max],dis[Max],vis[Max];
struct shu{int to,next,len;};
shu edge[Max<<2];

inline int get_int()
{
	int x=0,f=1;
	char c;
	for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
	if(c=='-') {f=-1;c=getchar();}
	for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
	return x*f;
}

inline int mx(int x,int y){return x > y ? x : y;}
inline int mn(int x,int y){return x > y ? y : x;}

inline void build(int x,int y,int z)
{
	edge[++size].next=first[x];
	first[x]=size;
	edge[size].to=y;
	edge[size].len=z;
//cout<<size<<"\n";
}

inline int SPFA()
{
	queue<int>q;
	memset(dis,-0x3f,sizeof(dis));
	q.push(s),dis[s]=0;
	while(!q.empty())
	{
	  int point = q.front();
	  q.pop(),vis[point] = 0;
	  for(int u=first[point];u;u=edge[u].next)
	  {
	  	int to=edge[u].to;
	  	if(dis[to] < dis[point] + edge[u].len)
	  	{
	  	  dis[to] = dis[point] + edge[u].len;
	  	  if(!vis[to])
	  	  {
	  	  	vis[to] = 1;
	  	  	q.push(to);
	  	  }
	  	}
	  }
	}
	return dis[t];
}

int main()
{
	n=get_int();
	for(int i=1;i<=n;i++)
	{
	  int x=get_int(),y=get_int(),z=get_int();
	  build(x-1,y,z);
	  s=mn(s,x),t=mx(t,y);
	}
	for(int i=s+1;i<=t;i++) build(i-1,i,0),build(i,i-1,-1);

	cout<<SPFA()<<"\n";
	return 0;
}