ZOJ 1508 poj 1201 Intervals 差分约束系统

比较巧妙的是令s[i]为集合Z中小于等于i的元素个数。
则得到不等式组s[ai-1] - s[bi] <= -ci;
还有隐含条件s[i] - s[i-1] <=1 && s[i]-s[i-1] >= 0

用Bellman写感觉还不错，清晰明了。抄书上的思路的。

贴代码：

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 #define MAXN 50005
 4 int n,min,max;
 5 struct Arc
 6 {
 7     int u,v,w;
 8 } edge[MAXN];
 9 int dist[MAXN];
10 int Bellman()
11 {
12     bool f = true;
13     int i,t;
14     memset(dist,0,sizeof(dist));
15     while(f)
16     {
17         f = false;
18         for(i=0; i<n; i++)
19         {
20             t = dist[edge[i].u]+edge[i].w;
21             if(dist[edge[i].v] > t)
22             {
23                 dist[edge[i].v] = t;
24                 f = true;
25             }
26         }
27         for(i=min; i <= max; i++)
28         {
29             t = dist[i-1] + 1;
30             if(dist[i] > t)
31             {
32                 dist[i] = t;
33                 f = true;
34             }
35         }
36         for(i = max; i>= min; i--)
37         {
38             t = dist[i];
39             if(dist[i-1] > dist[i])
40             {
41                 dist[i-1] = t;
42                 f= true;
43             }
44         }
45     }
46     return  -dist[min-1];
47 }
48 int main()
49 {
50 //    freopen("in.cpp","r",stdin);
51     while(~scanf("%d",&n))
52     {
53         max = -1;
54         min = 100000;
55         for(int i=0; i<n; i++)
56         {
57             int u,v,w;
58             scanf("%d%d%d",&u,&v,&w);
59             if(v > max) max = v;
60             if(u < min) min = u;
61             edge[i].u = v;
62             edge[i].v = u-1;
63             edge[i].w = -w;
64         }
65         printf("%d\n",Bellman());
66     }
67     return 0;
68 }