转载请注明出处： http://www.cnblogs.com/fraud/ ——by fraud
Intervals
Time Limit: 10 Seconds Memory Limit: 32768 KB
You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn.
Write a program that:
> reads the number of intervals, their endpoints 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 <= 50 000) - 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 <= 50 000 and 1 <= ci <= bi
- ai + 1.
Process to the end of file.
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
题意：
对于一个序列，有n个描述，[ai,bi,ci]分别表示在区间[ai,bi]上，至少有ci个数属于该序列。输出满足这n个条件的最短的序列（即包含的数字个数最少）
分析：
设s[i]表示从0到i中有s[i]个数属于这个序列。
那么，对于每个描述，都可以得到一个方程s[bi]-s[ai-1]>=ci
同时由于每个数至多取一次，那么有s[i]-s[i-1]<=1,即s[i-1]-s[i]>=-1;
另外还有s[i]-s[i-1]>=0;
由这三个方程组建图，利用最长路即可求出。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#define MAXN 50010
#define REP(A,X) for(int A=0;A<X;A++)
#define INF 0x7fffffff
#define CLR(A,X) memset(A,X,sizeof(A))
struct node {
int v,d,next;
}edge[*MAXN];
int head[MAXN];
int e=;
void init()
{
REP(i,MAXN)head[i]=-;
}
void add_edge(int u,int v,int d)
{
edge[e].v=v;
edge[e].d=d;
edge[e].next=head[u];
head[u]=e;
e++;
}
bool vis[MAXN];
int dis[MAXN];
void spfa(int s){
CLR(vis,);
REP(i,MAXN)dis[i]=i==s?:INF;
queue<int>q;
q.push(s);
vis[s]=;
while(!q.empty())
{
int x=q.front();
q.pop();
int t=head[x];
while(t!=-)
{
int y=edge[t].v;
int d=edge[t].d;
t=edge[t].next;
if(dis[y]>dis[x]+d)
{
dis[y]=dis[x]+d;
if(vis[y])continue;
vis[y]=;
q.push(y);
}
}
vis[x]=;
}
}
int main()
{
ios::sync_with_stdio(false);
int n;
int u,v,d;
int ans=;
int maxn=;
int minn=MAXN;
while(scanf("%d",&n)!= EOF&&n)
{
e=;
init();
REP(i,n)
{
scanf("%d%d%d",&u,&v,&d);
add_edge(u,v+,-d);
maxn=max(maxn,v+);
minn=min(u,minn);
}
for(int i=minn;i<maxn;i++){
add_edge(i+,i,);
add_edge(i,i+,);
}
spfa(minn);
cout<<-dis[maxn]<<endl;
}
return ;
}
代码君