Integer Intervals
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 9285
Accepted: 3898
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.
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.
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<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=10000+10;
struct edge
{
int t,w;
int next;
};
int p[maxn];
edge G[maxn*6];
int l;
void init()
{
l=0;
memset(p,-1,sizeof(p));
}
void addedge(int u,int t,int w,int l)
{
G[l].t=t;
G[l].w=w;
G[l].next=p[u];
p[u]=l;
}
int V,E;
int det,src;
bool v[maxn];
int dis[maxn];
int que[maxn],front,rear;
int inque[maxn];
bool vis[maxn];
bool spfa(int s0)
{
memset(vis,0,sizeof(vis));
memset(inque,0,sizeof(inque));
front=rear=0;
for(int i=src;i<=det;i++)
{
dis[i]=maxn*100;
}dis[s0]=0;
que[rear++]=s0;inque[s0]++;vis[s0]=true;
while(front!=rear)
{
int u=que[front++];
if(front==maxn) front=0;
vis[u]=0;
for(int i=p[u];i!=-1;i=G[i].next)
{
int t=G[i].t,w=G[i].w;
if(dis[t]>dis[u]+w)
{
dis[t]=dis[u]+w;
if(vis[t]==0)
{
que[rear++]=t;
if(rear==maxn) rear=0;
vis[t]=1;
inque[t]++;
if(inque[t]>V) return false;
}
}
}
}
return true;
}
int main()
{
int n;
while(scanf("%d",&n)==1)
{
init();
det=-1,src=maxn;
for(int i=0;i<n;i++)
{
int a,b;scanf("%d%d",&a,&b);a+=2,b+=2;
//b-(a-1)>=2
//(a-1)-b<=-2;
//b->a-1 -2;
a--;
det=max(det,a);det=max(det,b);
src=min(src,a),src=min(src,b);
addedge(b,a,-2,l++);
}
//0<=i+1-i<=1
for(int i=1;i<=det;i++)
{
addedge(i,i+1,1,l++);
addedge(i+1,i,0,l++);
}
//增加源点0
V=det;
for(int i=src;i<=det;i++)
{
//0->i 0
addedge(0,i,0,l++);
}
spfa(0);
printf("%d\n",dis[det]-dis[src]);
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)