poj 1716 Integer Intervals（差分约束）

　　跟之前个人赛的一道二分加差分约束差不多，也是求满足条件的最小值。

　　题意是，给出若干区间，需要找出最少的元素个数，使得每个区间至少包含两个这里的元素。

　　做法就是建立(b)->(a)=-2，(i)->(i+1)=1，(i+1)->(i)=0的边，然后跑一次spfa即可。

　　做完的时候，因为队列开太小，所以re了一次。

代码如下：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 
 8 const int N = 11111;
 9 struct Edge {
10     int t, nx, c;
11     Edge() {}
12     Edge(int t, int nx, int c) : t(t), nx(nx), c(c) {}
13 } edge[N << 2];
14 int eh[N], ec;
15 
16 void init() {
17     memset(eh, -1, sizeof(eh));
18     ec = 0;
19 }
20 
21 void addedge(int s, int t, int c) {
22     edge[ec] = Edge(t, eh[s], c);
23     eh[s] = ec++;
24 }
25 
26 int q[N << 8], dis[N];
27 bool vis[N];
28 
29 int spfa(int s, int t) {
30     memset(vis, 0, sizeof(vis));
31     memset(dis, 127, sizeof(dis));
32     int qh, qt, cur;
33     qh = qt = 0;
34     q[qt++] = s;
35     vis[s] = true;
36     dis[s] = 0;
37     while (qh < qt) {
38         //cout << cur << endl;
39         cur = q[qh++];
40         vis[cur] = false;
41         for (int i = eh[cur]; ~i; i = edge[i].nx) {
42             //cout << i << endl;
43             Edge &e = edge[i];
44             if (dis[e.t] > dis[cur] + e.c) {
45                 dis[e.t] = dis[cur] + e.c;
46                 q[qt++] = e.t;
47                 vis[e.t] = true;
48             }
49         }
50     }
51     return dis[t];
52 }
53 
54 int main() {
55     int n, x, y;
56     while (~scanf("%d", &n)) {
57         init();
58         int mn = 11111111, mx = -11111111;
59         for (int i = 0; i < n; i++) {
60             scanf("%d%d", &x, &y);
61             addedge(y + 1, x, -2);
62             mn = min(mn, x);
63             mx = max(mx, y + 1);
64         }
65         for (int i = 0; i <= 10000; i++) {
66             addedge(i, i + 1, 1);
67             addedge(i + 1, i, 0);
68         }
69         printf("%d
", -spfa(mx, mn));
70     }
71     return 0;
72 }

View Code

——written by Lyon