转载请注明出处： http://www.cnblogs.com/fraud/ ——by fraud
Integer Intervals
| Time Limit: 1000MS | Memory Limit: 10000K |
Description
An integer interval [a,b], a < b, is a set of all consecutive integers beginning with a and ending with b.
Write a program that: finds the minimal number of elements in a set
containing at least two different integers from each interval.
Write a program that: finds the minimal number of elements in a set
containing at least two different integers from each interval.
Input
The
first line of the input contains the number of intervals n, 1 <= n
<= 10000. Each of the following n lines contains two integers a, b
separated by a single space, 0 <= a < b <= 10000. They are the
beginning and the end of an interval.
first line of the input contains the number of intervals n, 1 <= n
<= 10000. Each of the following n lines contains two integers a, b
separated by a single space, 0 <= a < b <= 10000. They are the
beginning and the end of an interval.
Output
Output the minimal number of elements in a set containing at least two different integers from each interval.
Sample Input
4
3 6
2 4
0 2
4 7
Sample Output
4
上一题差分约束的阉割版（传送门）
#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",&u,&v);
add_edge(u,v+,-);
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 ;
}
代码君