题意:给出N个整数区间[ai,bi],使得序列在区间[ai,bj]的个数>=2个,求出序列的最小长度
如样例:
3 6
2 4
0 2
4 7
所对应的序列为:1 2 4 5
思路: dis[i] 表示 [0,i)中的元素个数,所以有 dis[v]-dis[u] >= 2
还有个隐含条件 1>=dis[i+1]-dis[i]>=0
用spfa 实现,因为有负环所以用栈结构,队列是457MS 栈是32MS
852K
32MS
#include <stdio.h>
#include <string.h>
#define EM 40000
#define VM 10005
#define inf -10000000
struct edge
{
int
v,w,next;
}e[EM];
int head[VM],ep;
void a......
阅读全文