poj 1201 Intervals(差分约束)

题意：给定n组数据，每组有ai,bi,ci，要求在区间[ai,bi]内至少找ci个数，并使得找的数字组成的数组Z的长度最小。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cstdlib>
 6 using namespace std;
 7 
 8 const int INF = 1<<28;
 9 struct node
10 {
11     int u;
12     int v;
13     int w;
14     int next;
15 }edge[50010];
16 int dis[50010];
17 int mi,ma,n;
18 
19 void bellman_ford()
20 {
21    int i,f=1;
22    while(f)
23    {
24        f=0;
25        for(i=1; i<=n; i++)
26        if(dis[edge[i].u]>dis[edge[i].v]-edge[i].w)
27        {
28            dis[edge[i].u]=dis[edge[i].v]-edge[i].w;
29            f=1;
30        }
31 
32        for(i=mi; i<=ma; i++)
33        if(dis[i]>dis[i-1]+1)
34        {
35            dis[i]=dis[i-1]+1;
36            f=1;
37        }
38 
39        for(i=ma; i>=mi; i--)
40        if(dis[i-1]>dis[i])
41        {
42            dis[i-1]=dis[i];
43            f=1;
44        }
45    }
46 }
47 
48 int main()
49 {
50     int i;
51     while(~scanf("%d",&n))
52     {
53         mi=INF;  ma=-1;
54         for(i=1; i<=n; i++)
55         {
56             scanf("%d%d%d",&edge[i].u, &edge[i].v, &edge[i].w);
57             if(mi>edge[i].u)
58             mi=edge[i].u;
59             if(ma<edge[i].v)
60             ma=edge[i].v;
61 
62             edge[i].u--;
63             dis[i]=0;
64         }
65         bellman_ford();
66        printf("%d
",dis[ma]-dis[mi-1]);
67     }
68     return 0;
69 }

大神的题解：

差分约束的思想：可以肯定的是s[bi]-s[ai-1]>=ci; 为什么要ai-1，是因为ai也要选进来
在一个是s[i]-s[i-1]<=1;
s[i]-s[i-1]>=0
所以整理上面三个式子可以得到约束条件：
①s[ai-1]-s[bi] <= -ci
②s[i]-s[i-1] <= 1
③s[i-1]-s[i] <= 0

1、约束条件必须同为<= 或者同为>=

2、若形如：x1 - x2<=k1 则 x2点向x1点连边，权值为k1，求最短路

若形如：x1-x2>=k1 则 x2点向x1点连边，权值为k1，求最长路

3、如果多组约束存在矛盾，则图中存在负环，判断负环的方法是用spfa判断是否有点进队次数>=n