http://acm.hdu.edu.cn/showproblem.php?pid=1384
Intervals
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4638 Accepted Submission(s): 1765
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
Process to the end of file.
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
题目大意：给若干个区间，并且每个区间给定一个数C，表示集合S至少含有这个区间内C个整数，求满足要求的S的最小元素数
题目分析：典型的差分约束题目，即能根据题设条件列出若干不等式，并且所求问题中含有最小【或最大，最多，最少】字眼。都可以列出不等式，然后转化为最短路或者最长路。
本题要求区间【LI,RI】内含有CI个整数，即可令S【I】表示最终集合S在【0，I】区间内含有的整数，则本题要求即可化为S【RI】-S【LI-1】>= CI【条件不等式一】
又因为S【I】-S【I-1】>= 0 && S【I】-S【I-1】<= 1【条件不等式二、三】
题目所求最小元素数ANS 即S【Rmax】-s【Lmin-1】>= ANS 【所求不等式】
由所求不等式确定所求最长路还是最短路，从而据此再根据条件不等式可以建图，SPFA跑一遍即可。
【PS：边的结构体数组一定要开大一点，不然会TLE到怀疑人生...】
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int INF=;
struct edge{
int to;
int len;
int next;
}EDGE[];
queue<int>pq;
int edge_cnt=,dist[],stk[],head[],n;
void add(int x,int y,int z)
{
EDGE[edge_cnt].to=y;
EDGE[edge_cnt].next=head[x];
EDGE[edge_cnt].len=z;
head[x]=edge_cnt++;
}
void spfa()
{
while(!pq.empty())
{
int qwq=pq.front();pq.pop();
stk[qwq]=;
for(int i = head[qwq] ; i != - ; i = EDGE[i].next)
{
int v=EDGE[i].to;
if(dist[v]<dist[qwq]+EDGE[i].len)
{
dist[v]=dist[qwq]+EDGE[i].len;
if(!stk[v]){
stk[v]=;
pq.push(v);
}
}
}
}
}
int main()
{
while(scanf("%d",&n)==)
{
edge_cnt=;
int mmin=;
int mmax=-;
memset(dist,-,sizeof(dist));
memset(stk,,sizeof(stk));
memset(head,-,sizeof(head));
while(!pq.empty())pq.pop();
while(n--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(a)
add(a-,b,c);
else
{
add(,b,c);
}
mmax=max(b,mmax);
mmin=min(a,mmin);
}
if(mmin==)
{
dist[]=;
add(,,);
add(,,-);
mmin=;
stk[]=;
pq.push();
}
else
{
stk[mmin-]=;
pq.push(mmin-);
dist[mmin-]=;
}
for(int i = mmin-;i<mmax;i++)
{
add(i+,i,-);
add(i,i+,);
}
spfa();
printf("%d\n",dist[mmax]);
}
return ;
}