Integer Intervals
Time Limit: 1000MS Memory Limit: 10000KTotal Submissions: 15647 Accepted: 6631
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建图不要用vector，这道题会T；
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
const int MAX = 100007;
const int INF = 0x3f3f3f3f;
struct node{
int to, c, next;
node() {}
node(int to, int c, int next) : to(to), c(c), next(next) {}
}e[MAX];
int head[MAX];
int dis[MAX], vis[MAX];
queue <int> q;
int cnt = 0;
void add(int x, int y, int z){
e[cnt] = {y, z, head[x]};
head[x] = cnt++;
}
int mn, mx;
int spfa()
{
fill(dis + mn + 1, dis + mx + 1, -INF);
vis[mn] = 1;
q.push(mn);
while(!q.empty())
{
int u = q.front();
q.pop();
vis[u] = 0;
for(int i = head[u]; i != -1; i = e[i].next)
{
int to = e[i].to;
int c = e[i].c;
if(dis[to] < dis[u] +c)
{
dis[to] = dis[u] + c;
if(!vis[to])
{
q.push(to);
vis[to] = 1;
}
}
}
}
return dis[mx];
}
int main(){
int n;
scanf("%d", &n);
memset(head, -1, sizeof head);
mx = -INF, mn = INF;
for(int i = 0, x, y; i < n; i++){
scanf("%d%d", &x, &y);
y++;
add(x, y, 2);
mn = min(x, mn), mx = max(mx, y);
}
for(int i = mn; i <= mx; i++){
add(i, i + 1, 0);
add(i + 1, i, -1);
}
printf("%d\n", spfa());
return 0;
}
