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
Source: Southwestern Europe 2002
//2013-11-25 09:45:31 Accepted 1508 C++ 2120 2124
/* 题意：
有一个序列，题目用n个整数组合 [ai，bi，ci]来描述它，[ai，bi，ci]表示在该
序列中处于[ai，bi]这个区间的整数至少有ci个。如果存在这样的序列，请求出满足
题目要求的最短的序列长度是多少。如果不存在则输出 -1。 差分约束：
第一题差分约束，感觉还好，基本看过资料的应该都可以做。
难点在于构图部分，构好图后直接求其单源最短路径。
构图就是要满足
1)S(bi) - S(a(i-1))>=Ci
2)Si - S(i-1)>=0
3)S(i-1) - Si>=-1 即 map[bi][a(i-1)]=-ci
map[i][i-1]=0
map[i-1][i]=1 然后在采用最短路算法求点n到点0的最短路，值再取反即为解
存在负权环时不存在 */
#include<stdio.h>
#include<string.h>
#define N 50005
#define inf 0x7ffffff
using namespace std;
struct node{
int u,v,w;
}edge[*N];
int n,edgenum,m;
int d[N];
int Max(int a,int b)
{
return a>b?a:b;
}
void addedge(int u,int v,int w)
{
edge[edgenum].u=u;
edge[edgenum].v=v;
edge[edgenum++].w=w;
}
bool bellman_ford()
{
bool flag;
for(int i=;i<=m;i++) d[i]=inf;
d[m]=;
for(int i=;i<m;i++){
flag=false;
for(int j=;j<edgenum;j++){
if(d[edge[j].u]!=inf && d[edge[j].v]>d[edge[j].u]+edge[j].w){
flag=true;
d[edge[j].v]=d[edge[j].u]+edge[j].w;
}
}
if(!flag) break;
}
for(int i=;i<edgenum;i++)
if(d[edge[i].u]!=inf && d[edge[i].v]>d[edge[i].u]+edge[i].w)
return false;
return true;
}
int main(void)
{
int a,b,c;
while(scanf("%d",&n)!=EOF)
{
edgenum=;
m=;
for(int i=;i<n;i++){
scanf("%d%d%d",&a,&b,&c);
addedge(b,a-,-c);
m=Max(m,Max(a,b));
}
for(int i=;i<m;i++){
addedge(i,i+,);
addedge(i+,i,);
}
if(!bellman_ford()) puts("-1");
else printf("%d\n",-d[]);
}
return ;
}
贴一下SPFA的解法：
//2013-11-25 22:05:24 Accepted 1508 C++ 130 5444
#include<iostream>
#include<vector>
#include<queue>
#include<stdio.h>
#include<string.h>
#define N 50005
#define inf 0x7ffffff
using namespace std;
struct node{
int v,w;
node(int a,int b){
v=a;w=b;
}
};
vector<node>V[N];
int d[N],vis[N],in[N];
int n,m;
int spfa()
{
memset(vis,,sizeof(vis));
memset(in,,sizeof(in));
for(int i=;i<=m;i++) d[i]=-inf;
queue<int>Q;
Q.push(m);
d[m]=;
while(!Q.empty()){
int u=Q.front();
Q.pop();
if(in[u]>m) return ;
vis[u]=;
int n0=V[u].size();
for(int i=;i<n0;i++){
int v=V[u][i].v;
int w=V[u][i].w;
if(d[v]<d[u]+w){
d[v]=d[u]+w;
if(!vis[v]){
in[v]++;
Q.push(v);
vis[v]=;
}
}
}
}
return ;
}
int main(void)
{
int a,b,c;
while(scanf("%d",&n)!=EOF)
{
m=;
for(int i=;i<N;i++) V[i].clear();
for(int i=;i<n;i++){
scanf("%d%d%d",&a,&b,&c);
m=max(m,max(a,b));
V[b].push_back(node(a-,c));
}
for(int i=;i<m;i++){
V[i].push_back(node(i+,-));
V[i+].push_back(node(i,));
}
if(!spfa()) puts("impossible");
else printf("%d\n",d[]);
}
return ;
}