題目：http://poj.org/problem?id=1201
Intervals
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 24502 Accepted: 9317
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
題意：要求滿足bi-ai選數(shù)>=ci 中最小的集合；
思路：
如題：s[n]代表前n當選最小的集合，可得：
s[bi]-s[ai-1]>=ci;（題）
s[I+1]-s[I]>=0;（本身）
s[I+1]-s[I]<=1;-->s[l]-s[I+1]>=-1（本身）用最小值建邊spfa求maxn-minn的最長路便可；
代碼：
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
int head[60005],val[160005];
int tot,to[160005],nex[160005];
int n;
int aa,bb,cc;
queue<int> q;
int d[60005];
int vis[60005];
void spfa(int x)
{
memset(d,-1,sizeof(d));
d[x]=0;
vis[x]=1;
q.push(x);
while(!q.empty())
{
int now=q.front();
q.pop();
vis[now]=0;
for(int i=head[now];i!=-1;i=nex[i])
{
int v=to[i];
if(d[v]==-1||d[v]<d[now]+val[i])
{
d[v]=d[now]+val[i];
if(!vis[v])
{
vis[v]=1;
q.push(v);
}
}
}
}
}
void add(int x,int y,int v)
{
int tmp=head[x];
head[x]=++tot;
nex[tot]=tmp;
to[tot]=y;
val[tot]=v;
}
int main()
{
scanf("%d",&n);
int minn=10000000;
int maxn=-10000000;
memset(head,-1,sizeof(head));
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&aa,&bb,&cc);
aa--;
add(bb,aa,cc);
minn=min(aa,minn);
maxn=max(maxn,bb);
}
for(int i=minn;i<maxn;i++)
{
add(i+1,i,0);
add(i,i+1,-1);
}
spfa(maxn);
printf("%d\n",d[minn]);
}
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學習，原版權(quán)很多不明，如有侵權(quán)請聯(lián)系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權(quán)所有
