【題意】：給出一個數集合Z與n個區間,每個區間表示為[ai,bi,ci].[ai,bi,ci]表示閉區間[ai,bi]與Z至少有ci個相同的數，求出數集Z可能的最少元素個數。
 
【題解】：從題目中，我們可以抽象出一大堆約束條件，并且ci的定義上明顯包含著不等關系。于是可以利用差分約束模型來解決。
             •(1) [ai,bi,ci]中,ai和bi最小可以取到0,為了方便，把所有的ai,bi都+1.
             •(2) 定義d[i]為閉區間[1,i]中與集合Z中共同元素的個數.要求Z的元素個數最少,就是要求d[max{bi}]-d[0]最小.
             •(3) 分析不等關系：
                  對于[ai,bi,ci],有d[bi]-d[ai-1] >= ci
                  對于每個i,有1 >= d[i]-d[i-1] >= 0

【代碼】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "queue"
 5 using namespace std;
 6 const int inf = 1 << 30;
 7 #define maxn 50500
 8 #define maxm 500000
 9 int n, m, l, r;
10 int eh[maxn], tot, dist[maxn];
11 bool visit[maxn];
12 struct Edge {
13     int u, v, w, next;
14 }et[maxm];
15 
16 void init() {
17     tot = 0;
18     memset(eh, -1, sizeof(eh));
19 }
20 
21 void addedge(int u, int v, int w) {
22     Edge e = {u, v, w, eh[u]};
23     et[tot] = e;
24     eh[u] = tot++;
25 }
26 
27 void spfa(int s) {
28     queue<int> que;
29     fill(&dist[0], &dist[maxn], -inf);
30     memset(visit, false, sizeof(visit));
31     dist[s] = 0, visit[s] = true;
32     que.push(s);
33     while(!que.empty()) {
34         int u = que.front();
35         que.pop();
36         visit[u] = false;
37         for(int i = eh[u]; i !=- 1; i = et[i].next) {
38             int v = et[i].v, w = et[i].w;
39             if(dist[v] < dist[u] + w) {
40                 dist[v] = dist[u] + w;
41                 if(!visit[v]) {
42                     que.push(v);
43                     visit[v] = true;
44                 }
45             }
46         }
47     }
48 }
49 
50 int main() {
51     int a, b, c;
52     while(~scanf("%d", &n)) {
53         init();
54         r = 0;
55     //    l = inf;
56         for(int i = 0; i < n; i++) {
57             scanf("%d%d%d", &a, &b, &c);
58             r = max(r, ++b);
59     //        l = min(l, a);
60             addedge(a, b, c);
61         }
62         for(int i = 1; i <= r; i++) {
63             addedge(i - 1, i, 0);
64             addedge(i, i - 1, -1);
65         }
66         spfa(0);
67         printf("%d\n", dist[r]);
68     }
69     return 0;
70 }