大致题意： 给出数轴上的n个区间，每个区间都是连续的int区间。 现在要在数轴上任意取一堆元素，构成一个元素集合V 要求每个区间和元素集合V的交集至少有两个不同的元素 求集合V最小的元素个数。
差分约束＋spfa跑最大流
#include"queue" #include"cstdio" #include"cctype" #include"cstring" #include"iostream" #include"algorithm" #define M 200000 using namespace std; int n , m; int ind[M] , e[M] , nex[M] , dis[M] , vis[M] , lon[M] , tot , e_; int ma(int a , int b){return a > b ? a : b;} inline int read(){ int lwd = 0 , pos = 1; static char ysy; for(;!isdigit(ysy) && ysy != '-';ysy = getchar()); if(ysy == '-')pos = -1 , ysy = '0'; for(; isdigit(ysy);ysy = getchar()) lwd = lwd * 10 + ysy - '0'; return lwd * pos; } inline void add(int a , int b , int c){ nex[++tot] = ind[a]; e[ind[a] = tot] = b; lon[tot] = c; } void spfa(){ memset(dis,-100,sizeof dis); queue <int>qu; dis[0] = 0; qu.push(0); while(!qu.empty()){ int v = qu.front(); qu.pop(); vis[v] = 0; for(int i = ind[v] ; i ; i = nex[i]){ if(dis[e[i]] < dis[v] + lon[i]){ dis[e[i]] = dis[v] + lon[i]; if(!vis[e[i]]){ qu.push(e[i]); vis[e[i]] = 1; } } } } } int main(){ n = read(); for(int i = 1 ; i <= n ; i++){ int a, b; //scanf("%d%d",&a,&b); a = read() , b = read(); add(a , b+1 , 2); e_ = ma(e_ , b+1); } for(int i = 0 ; i < e_;i++){ add(i , i+1 , 0); add(i+1 , i ,-1); } spfa(); printf("%d",dis[e_]); return 0; }