差分约束

我的理解：

给定一个变量如X0（类似于物理的参照物），求所有Xk-X0的最大值Dk。

如：

Xa-X0<=Dk，

如果Xb-Xa<=L，则有

Xb-X0<=Dk+L，

对于Xb-Xa<=L，

变形为Xa+L>=Xb，

(Xa-X0)+L>=(Xb-X0)

Da+L>=Db

相当于点a到点b有一条长度为L的有向边，当Da+L>=b，点b的最短路修改为从起点到点a的最短路+点a到点b。

求最短路后，相当于求出Xk-X0<=V中，V的最小值(其它V都无意义，Xk-X0<=V<=any V')。这就是Xk-X0的最大值（它不能取大于V的值，否则式子Xk-X0<=V不成立）。

study from：

https://blog.csdn.net/my_sunshine26/article/details/72849441

https://blog.csdn.net/lyy289065406/article/details/6648679

 题目：

1.

http://poj.org/problem?id=1716

study from：https://blog.csdn.net/lyy289065406/article/details/6648679

贪心

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <time.h>
 6 #include <string>
 7 #include <set>
 8 #include <map>
 9 #include <list>
10 #include <stack>
11 #include <queue>
12 #include <vector>
13 #include <bitset>
14 #include <algorithm>
15 #include <iostream>
16 using namespace std;
17 #define ll long long
18 #define minv 1e-6
19 #define inf 1e9
20 #define pi 3.1415926536
21 #define nl 2.7182818284
22 const ll mod=1e9+7;//998244353
23 const int maxn=1e4+10;
24 
25 struct node
26 {
27     int a,b;
28 }f[maxn];
29 
30 bool vis[maxn]={0};
31 
32 int cmp(node x,node y)
33 {
34     if (x.b==y.b)
35         return x.a<y.a;
36     else
37         return x.b<y.b;
38 }
39 
40 int main()
41 {
42     int n,i,sum=0,x,y;
43     scanf("%d",&n);
44     for (i=1;i<=n;i++)
45         scanf("%d%d",&f[i].a,&f[i].b);
46     sort(f+1,f+n+1,cmp);
47     x=-1,y=-1;
48     for (i=1;i<=n;i++)
49     {
50         if (y<f[i].a)
51             y=f[i].b,sum++;
52         if (x<f[i].a)
53         {
54             sum++;
55             if (y!=f[i].b)
56             {
57                 x=y;
58                 y=f[i].b;
59             }
60             else
61                 x=f[i].b-1;
62         }
63     }
64     cout<<sum;
65     return 0;
66 }

sum[b]-sum[a-1]>=2
sum[b]-2>=sum[a-1]
b -> a-1    len=-2

sum[x+1]+0>=sum[x]
x+1 -> x    len=0

sum[x]+1>=sum[x+1]
x -> x+1    len=1

第三个式子容易忘

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <time.h>
  6 #include <string>
  7 #include <set>
  8 #include <map>
  9 #include <list>
 10 #include <stack>
 11 #include <queue>
 12 #include <vector>
 13 #include <bitset>
 14 #include <algorithm>
 15 #include <iostream>
 16 using namespace std;
 17 #define ll long long
 18 #define minv 1e-6
 19 #define inf 1e9
 20 #define pi 3.1415926536
 21 #define nl 2.7182818284
 22 const ll mod=1e9+7;//998244353
 23 const int maxn=1e4+10;
 24 
 25 /*
 26 sum[b]-sum[a-1]>=2
 27 sum[b]-2>=sum[a-1]
 28 b -> a-1    len=-2
 29 
 30 sum[x+1]+0>=sum[x]
 31 x+1 -> x    len=0
 32 
 33 sum[x]+1>=sum[x+1]
 34 x -> x+1    len=1
 35 */
 36 
 37 struct node
 38 {
 39     int d,len;
 40     node *next;
 41 }*prenode[10],*e[maxn];
 42 
 43 int preint[10],dist[maxn],q[maxn];
 44 bool vis[maxn]={0};
 45 
 46 int main()
 47 {
 48     node *p;
 49     int n,i,a,b,head,tail,d,dd,value=10000;
 50     scanf("%d",&n);
 51     for (i=1;i<=n;i++)
 52     {
 53         scanf("%d%d",&a,&b);
 54         p=(node*) malloc (sizeof(node));
 55         p->d=a-1;
 56         p->len=-2;
 57         p->next=e[b];
 58         e[b]=p;
 59     }
 60     for (i=0;i<=value;i++)
 61     {
 62         p=(node*) malloc (sizeof(node));
 63         p->d=i-1;
 64         p->len=0;
 65         p->next=e[i];
 66         e[i]=p;
 67     }
 68     for (i=-1;i<=value-1;i++)
 69     {
 70         p=(node*) malloc (sizeof(node));
 71         p->d=i+1;
 72         p->len=1;
 73         p->next=e[i];
 74         e[i]=p;
 75     }
 76     fill(dist-1,dist+value,inf);
 77     dist[value]=0;
 78     fill(vis-1,vis+value,0);
 79     vis[value]=1;
 80     head=0,tail=1;
 81     q[1]=value;
 82     while (head!=tail)
 83     {
 84         head=(head+1)%10001;
 85         d=q[head];
 86         p=e[d];
 87         while (p)
 88         {
 89             dd=p->d;
 90             if (dist[dd]>dist[d]+p->len)
 91             {
 92                 dist[dd]=dist[d]+p->len;
 93                 if (!vis[dd])
 94                 {
 95                     vis[dd]=1;
 96                     tail=(tail+1)%10001;
 97                     q[tail]=dd;
 98                 }
 99             }
100             p=p->next;
101         }
102         vis[d]=0;
103     }
104     printf("%d",-dist[-1]);
105     return 0;
106 }

2.

http://poj.org/problem?id=1201

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <time.h>
  6 #include <string>
  7 #include <set>
  8 #include <map>
  9 #include <list>
 10 #include <stack>
 11 #include <queue>
 12 #include <vector>
 13 #include <bitset>
 14 #include <algorithm>
 15 #include <iostream>
 16 using namespace std;
 17 #define ll long long
 18 #define minv 1e-6
 19 #define inf 1e9
 20 #define pi 3.1415926536
 21 #define nl 2.7182818284
 22 const ll mod=1e9+7;//998244353
 23 const int maxn=5e4+10;
 24 
 25 /*
 26 sum[b]-sum[a-1]>=2
 27 sum[b]-2>=sum[a-1]
 28 b -> a-1    len=-2
 29 
 30 sum[x+1]+0>=sum[x]
 31 x+1 -> x    len=0
 32 
 33 sum[x]+1>=sum[x+1]
 34 x -> x+1    len=1
 35 */
 36 
 37 struct node
 38 {
 39     int d,len;
 40     node *next;
 41 }*prenode[10],*e[maxn];
 42 
 43 int preint[10],dist[maxn],q[maxn];
 44 bool vis[maxn]={0};
 45 
 46 int main()
 47 {
 48     node *p;
 49     int n,i,a,b,c,head,tail,d,dd,value=50000;
 50     scanf("%d",&n);
 51     for (i=1;i<=n;i++)
 52     {
 53         scanf("%d%d%d",&a,&b,&c);
 54         p=(node*) malloc (sizeof(node));
 55         p->d=a-1;
 56         p->len=-c;
 57         p->next=e[b];
 58         e[b]=p;
 59     }
 60     for (i=0;i<=value;i++)
 61     {
 62         p=(node*) malloc (sizeof(node));
 63         p->d=i-1;
 64         p->len=0;
 65         p->next=e[i];
 66         e[i]=p;
 67     }
 68     for (i=-1;i<=value-1;i++)
 69     {
 70         p=(node*) malloc (sizeof(node));
 71         p->d=i+1;
 72         p->len=1;
 73         p->next=e[i];
 74         e[i]=p;
 75     }
 76     fill(dist-1,dist+value,inf);
 77     dist[value]=0;
 78     fill(vis-1,vis+value,0);
 79     vis[value]=1;
 80 
 81     head=0,tail=1;
 82     q[1]=value;
 83     while (head!=tail)
 84     {
 85         head=(head+1)%50001;
 86         d=q[head];
 87         p=e[d];
 88         while (p)
 89         {
 90             dd=p->d;
 91             if (dist[dd]>dist[d]+p->len)
 92             {
 93                 dist[dd]=dist[d]+p->len;
 94                 if (!vis[dd])
 95                 {
 96                     vis[dd]=1;
 97                     tail=(tail+1)%50001;
 98                     q[tail]=dd;
 99                 }
100             }
101             p=p->next;
102         }
103         vis[d]=0;
104     }
105     printf("%d",-dist[-1]);
106     return 0;
107 }

3.

http://poj.org/problem?id=3169

BellmanFord

在这里，神奇地速度竟然比SPFA快

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <time.h>
  6 #include <string>
  7 #include <set>
  8 #include <map>
  9 #include <list>
 10 #include <stack>
 11 #include <queue>
 12 #include <vector>
 13 #include <bitset>
 14 //#include <ext/rope>
 15 #include <algorithm>
 16 #include <iostream>
 17 using namespace std;
 18 #define ll long long
 19 #define minv 1e-6
 20 #define inf 2e9
 21 #define pi 3.1415926536
 22 #define nl 2.7182818284
 23 const ll mod=1e9+7;//998244353
 24 const int maxn=1e4+10;
 25 
 26 /**
 27 a[y]-a[x]<=z
 28 a[x]+z>=a[y]
 29 x->y z
 30 
 31 a[y]-a[x]>=z
 32 a[y]-z>=a[x]
 33 y->x -z
 34 
 35 a[x+1]-a[x]>=0
 36 a[x+1]>=a[x]
 37 x+1->x 0
 38 **/
 39 
 40 struct rec
 41 {
 42     int x,y,z;
 43 }f[30000];///ml+md+n
 44 
 45 int dist[maxn],g=0;
 46 
 47 bool bell()
 48 {
 49     bool vis=0;
 50     int i;
 51     for (i=1;i<=g;i++)
 52         if (dist[f[i].y]>dist[f[i].x]+f[i].z)   ///don't need to judge ==inf !=inf
 53         {
 54             dist[f[i].y]=dist[f[i].x]+f[i].z;
 55             vis=1;
 56         }
 57     return vis;
 58 }
 59 
 60 int main()
 61 {
 62     int n,ml,md,i,x,y,z;
 63     scanf("%d%d%d",&n,&ml,&md);
 64     for (i=1;i<=ml;i++)
 65     {
 66         scanf("%d%d%d",&x,&y,&z);
 67         f[++g]={x,y,z};
 68     }
 69     for (i=1;i<=md;i++)
 70     {
 71         scanf("%d%d%d",&x,&y,&z);
 72         f[++g]={y,x,-z};
 73     }
 74 
 75     for (i=1;i<n;i++)
 76         f[++g]={i+1,i,0};
 77 
 78     fill(dist,dist+n+1,inf);
 79     dist[1]=0;
 80     for (i=1;i<=n;i++)
 81         if (!bell())
 82             break;
 83     if (i==n+1)
 84         printf("-1");
 85     else if (dist[n]==inf)
 86         printf("-2");
 87     else
 88         printf("%d",dist[n]);
 89     return 0;
 90 }
 91 /*
 92 4 2 0
 93 1 2 10
 94 3 4 20
 95 
 96 4 1 1
 97 1 2 8
 98 1 2 12
 99 
100 3 1 1
101 1 3 10
102 2 3 12
103 
104 4 1 1
105 2 3 8
106 2 3 12
107 */

SPFA

有些样例不对，因为如果使用SPFA，有些点不能到达，但代码通过了这题

如：

4 1 1
2 3 8
2 3 12
wrong!

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <time.h>
  6 #include <string>
  7 #include <set>
  8 #include <map>
  9 #include <list>
 10 #include <stack>
 11 #include <queue>
 12 #include <vector>
 13 #include <bitset>
 14 #include <ext/rope>
 15 #include <algorithm>
 16 #include <iostream>
 17 using namespace std;
 18 #define ll long long
 19 #define minv 1e-6
 20 #define inf 2e9
 21 #define pi 3.1415926536
 22 #define nl 2.7182818284
 23 const ll mod=1e9+7;//998244353
 24 const int maxn=1e3+10;
 25 
 26 /**
 27 a[y]-a[x]<=z
 28 a[x]+z>=a[y]
 29 x->y z
 30 
 31 a[y]-a[x]>=z
 32 a[y]-z>=a[x]
 33 y->x -z
 34 
 35 a[x+1]-a[x]>=0
 36 a[x+1]>=a[x]
 37 x+1->x 0
 38 **/
 39 
 40 struct node
 41 {
 42     int d,len;
 43     node *next;
 44 }*e[maxn];
 45 
 46 int dist[maxn],q[maxn],use[maxn];
 47 bool vis[maxn];
 48 
 49 int main()
 50 {
 51     node *p;
 52     int n,ml,md,i,x,y,z,d,dd,head,tail;
 53     scanf("%d%d%d",&n,&ml,&md);
 54     for (i=1;i<=ml;i++)
 55     {
 56         scanf("%d%d%d",&x,&y,&z);
 57         p=(node*) malloc (sizeof(node));
 58         p->d=y;
 59         p->len=z;
 60         p->next=e[x];
 61         e[x]=p;
 62     }
 63     for (i=1;i<=md;i++)
 64     {
 65         scanf("%d%d%d",&x,&y,&z);
 66         p=(node*) malloc (sizeof(node));
 67         p->d=x;
 68         p->len=-z;
 69         p->next=e[y];
 70         e[y]=p;
 71     }
 72     for (i=1;i<n;i++)
 73     {
 74         p=(node*) malloc (sizeof(node));
 75         p->d=i;
 76         p->len=0;
 77         p->next=e[i+1];
 78         e[i+1]=p;
 79     }
 80 
 81     fill(dist,dist+n+1,inf);
 82     dist[1]=0;
 83     memset(vis,0,sizeof(vis));
 84     vis[1]=1;
 85     memset(use,0,sizeof(use));
 86     q[1]=1;
 87     head=0;
 88     tail=1;
 89     while (head!=tail)
 90     {
 91         head=(head+1)%n;
 92         d=q[head];
 93         p=e[d];
 94         while (p)
 95         {
 96             dd=p->d;
 97             if (dist[dd]>dist[d]+p->len)
 98             {
 99                 dist[dd]=dist[d]+p->len;
100                 use[dd]++;
101                 if (use[dd]>=n)
102                 {
103                     printf("-1");
104                     return 0;
105                 }
106                 if (!vis[dd])
107                 {
108                     vis[dd]=1;
109                     tail=(tail+1)%n;
110                     q[tail]=dd;
111                 }
112             }
113             p=p->next;
114         }
115         vis[d]=0;
116     }
117     if (dist[n]==inf)
118         printf("-2");
119     else
120         printf("%d",dist[n]);
121     return 0;
122 }
123 /*
124 4 2 0
125 1 2 10
126 3 4 20
127 
128 4 1 1
129 1 2 8
130 1 2 12
131 
132 3 1 1
133 1 3 10
134 2 3 12
135 
136 4 1 1
137 2 3 8
138 2 3 12
139 wrong!
140 */
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/cmyg/p/9557681.html