POJ 1201 Intervals

此文为博主原创，转载时请通知博主，并把原文链接放在正文醒目位置。

题目链接：http://poj.org/problem?id=1201

题目大意：

有一个序列，题目用n个整数组合 [ai，bi，ci]来描述它，[ai，bi，ci]表示在该序列中处于[ai，bi]这个区间的整数至少有ci个。如果存在这样的序列，请求出满足题目要求的最短的序列长度是多少。

思路：

此题为差分约束

做题时遵循三个不等式

1.S[b] - S[a - 1] >= c

2.S[b] - s[b - 1] >= 0

3.S[b - 1] - S[b] >= -1

然后建图就ok了owo

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <queue>
 5 #include <cstring>
 6 using namespace std;
 7 const int MAXN = 500000 + 10;
 8 const int MAXM = 500000 * 3 + 10;
 9 int head[MAXN], L, R, n, len;
10 struct edge{
11     int to, next;
12     int val;
13 }e[MAXM];
14 inline int read(){
15     char ch, c;
16     int res;
17     while (ch = getchar(), ch < '0' || ch > '9') c = ch;
18     res = ch - 48;
19     while (ch = getchar(), ch >= '0' && ch <= '9')
20     res = (res << 3) + (res << 1) + ch - 48;
21     if (c == '-') res = -res;
22     return res;
23 }
24 void add(int from, int to, int val){
25     e[len].to = to;
26     e[len].val = val;
27     e[len].next = head[from];
28     head[from] = len++;
29 }
30 int dis[MAXN];
31 int vis[MAXN];
32 int spfa(){
33     queue<int> q;
34     for (int i = L; i <= R; i++){
35         dis[i] = 0;
36         vis[i] = 1;
37         q.push(i);
38     }
39     while (!q.empty()){
40         int cur = q.front();
41         q.pop();
42         vis[cur] = false;
43         for (int i = head[cur]; i != -1; i = e[i].next){
44             int id = e[i].to;
45             if (e[i].val + dis[cur] > dis[id]){
46                 dis[id] = e[i].val + dis[cur];
47                 if (!vis[id]){
48                     vis[id] = true;
49                     q.push(id);
50                 }
51             }
52         }
53     }
54     return dis[R];
55 }
56 int main(){
57     while (~scanf("%d", &n)){
58         memset(head, -1, sizeof(head));
59         R = len = 0;
60         L = 0x7fffff;
61         for (int i = 1; i <= n; i++){
62             int from, to, val;
63             scanf("%d%d%d", &from, &to, &val);
64             R = max(to + 1, R);
65             L = min(L, from);
66             add(from, to + 1, val);
67         }
68         for (int i = L; i <= R; i++){
69             add(i, i + 1, 0);
70             add(i + 1, i, -1);
71         }
72         printf("%d
", spfa());
73     }
74     return 0;
75 }