题目大意：给出N个区间，要求你找出M个数，这M个数满足在每个区间都至少有两个不同的数

解题思路：还是不太懂差分约束系统，数学不太好
借鉴了别人的思路，感觉有点DP思想
设d[i]表示[0,i-1]这个区间有d[i]个数满足要求
则给定一个区间[a,b]，就有d[b + 1] - d[a] >= 2(b + 1是因为b也算在区间内)
将其转换为d[a] - d[b + 1] <= -2,这是第一个式子
接着在区间[i,i+1]中满足
d[i + 1] - d[i] >= 0 转换为 d[i] - d[i +1] <= 0
d[i + 1] - d[i] <= 1
三个式子构图
以Max(最右边界＋1)为源点，进行SPFA
最后答案为d[Max] - d[Min]

#include 
   
     #include 
    
      #include 
     
       using namespace std; #define N 10010 #define M 30010 #define INF 0x3f3f3f3f struct Edge{ int dist, to, next; }E[M]; int head[N], d[N], n, tot; bool vis[N]; void AddEdge(int u, int v, int dist) { E[tot].to = v; E[tot].dist = dist; E[tot].next = head[u]; head[u] = tot++; } void SPFA(int s) { for (int i = 0; i <= s; i++) { d[i] = INF; vis[i] = 0; } queue
      
        q; q.push(s); d[s] = 0; while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for (int i = head[u]; i != -1; i = E[i].next) { int v = E[i].to; if (d[v] > d[u] + E[i].dist) { d[v] = d[u] + E[i].dist; if (!vis[v]) { vis[v] = true; q.push(v); } } } } } void solve() { memset(head, -1, sizeof(head)); tot = 0; int Min = INF, Max = -INF; int u, v; for (int i = 0; i < n; i++) { scanf(%d%d, &u, &v); Min = min(Min, u); Max = max(Max, v + 1); AddEdge(v + 1, u, -2); } for (int i = 0; i < Max; i++) { AddEdge(i, i + 1, 1); AddEdge(i + 1, i, 0); } SPFA(Max); printf(%d , d[Max] - d[Min]); } int main() { while (scanf(%d, &n) != EOF) { solve(); } return 0; } 
      
     
    
   

?