ZOJ2770(差分约束系统学习)

Sn代表前n个军营的总人数

3 2
1000 2000 1000
1 2 1100
2 3 1300
1.每个兵营实际人数不能超过其容量，得到下面不等式
S1 - S0 <= 1000
S2 - S1 <= 2000
S3 - S2 <= 1000
2.每个兵营的实际人数大于等于0，得到下面不等式
S0 - S1 <= 0
S1 - S2 <= 0
S2 - S3 <= 0 
3.第i个大营到第j个大营的士兵总数至少有k个，得到下面不等式
S0 - S2 <= -1100
S1 - S3 <= -1300
4.第i个大营到第j个大营的士兵总数不超过这些兵营容量的和，得到下面不等式
S2 - S0 <= 3000
S3 - S1 <= 3000
最终要求 Sn - S0 >= M , 转化为 S0 - S3 <= -M

1.Bellman_Ford 版本

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 using namespace std;
 7 #define inf 9999999
 8 #define N 1005
 9 #define M 23000
10 int n,m,size;
11 int c[N],dis[N],d[N];
12 struct Edge
13 {
14     int u,v,w;
15 }edge[M];
16 
17 void Init()
18 {
19     size = 0;
20     for(int i=0; i<=n; i++)
21     dis[i] = inf;
22     d[0] = 0; dis[n] = 0;
23 }
24 
25 bool Bellman_Ford()
26 {
27     for(int i=1; i<=n; i++) // 有 0~n个点，一共n+1个点 ，循环 n 次 
28     {
29         for(int k=0; k<size; k++)
30         {
31             int u = edge[k].u ;
32             int v = edge[k].v ;
33             int w = edge[k].w ;
34             if(dis[u] != inf && dis[u] + w < dis[v])
35             {
36                 dis[v] = dis[u] + w ;
37             }
38         }
39     }
40     for(int k=0; k<size; k++)
41     {
42         int u = edge[k].u ;
43         int v = edge[k].v ;
44         int w = edge[k].w ;
45         if(dis[u] != inf && dis[u] + w < dis[v]) return 0;
46     }
47     return 1;
48 }
49 
50 int main()
51 {
52     while(scanf("%d%d",&n,&m)!=EOF)
53     {
54         Init();
55         for(int i=1; i<=n; i++)
56         {
57             scanf("%d",&c[i]);
58             edge[size].u = i-1 ; edge[size].v = i ; edge[size++].w = c[i] ;
59             edge[size].u = i ; edge[size].v = i-1 ; edge[size++].w = 0 ;
60             d[i] = c[i] + d[i-1] ;
61         }
62         int u,v,w;
63         for(int i=1; i<=m; i++)
64         {
65             scanf("%d%d%d",&u,&v,&w);
66             edge[size].u = v ; edge[size].v = u-1 ; edge[size++].w = -w ; 
67             edge[size].u = u-1 ; edge[size].v = v ; edge[size++].w = d[v] - d[u-1] ;
68         }
69         if(!Bellman_Ford()) printf("Bad Estimations
");
70         else printf("%d
",dis[n] - dis[0]) ;
71     }
72     return 0;
73 }

View Code

2.SPFA 版本

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <queue>
 6 #include <algorithm>
 7 using namespace std;
 8 #define inf 9999999
 9 #define N 1005

10 #define M 23005
11 int size,n,m;
12 int dis[N],vis[N],head[N],in[N],sum[N];
13 struct Edge
14 {
15     int v,w,next;
16     Edge(){}
17     Edge(int V,int W,int NEXT):v(V),w(W),next(NEXT){}
18 }edge[M];
19 
20 void Init()
21 {
22     size = 0;
23     memset(head,-1,sizeof(head));
24     sum[0] = 0;
25 }
26 
27 void InsertEdge(int u,int v,int w)
28 {
29     edge[size] = Edge(v,w,head[u]);
30     head[u] = size++;
31 }
32 
33 bool spfa(int st)
34 {
35     for(int i=0; i<=n; i++)
36     {
37         vis[i] = 0;
38         dis[i] = inf;
39         in[i] = 0;
40     }
41     dis[st] = 0 ; vis[st] = 1;
42     queue<int> Q;
43     while(!Q.empty()) Q.pop();
44     Q.push(st);
45     in[st] ++;
46     while(!Q.empty())
47     {
48         int u = Q.front();
49         Q.pop();
50         vis[u] = 0;
51         for(int i=head[u]; i!=-1; i=edge[i].next)
52         {
53             int v = edge[i].v;
54             if(dis[v] > dis[u] + edge[i].w)
55             {
56                 dis[v] = dis[u] + edge[i].w;
57                 if(!vis[v])
58                 {
59                     vis[v] = 1;
60                     in[v]++;
61                     if(in[v] > n) return 0;
62                     Q.push(v);
63                 }
64             }
65         }
66     }
67     return 1;
68 }
69 
70 int main()
71 {
72     while(scanf("%d%d",&n,&m)!=EOF)
73     {
74         Init();
75         int u,v,w;
76         for(int i=1; i<=n; i++)
77         {
78             scanf("%d",&w);
79             InsertEdge(i-1,i,w);
80             InsertEdge(i,i-1,0);
81             sum[i] = sum[i-1] + w;
82         }
83         for(int i=0; i<m; i++)
84         {
85             scanf("%d%d%d",&u,&v,&w);
86             InsertEdge(v,u-1,-w);
87             InsertEdge(u-1,v,sum[v]-sum[u-1]);
88         }
89         if(!spfa(n))  printf("Bad Estimations
");
90         else  printf("%d
",-dis[0]);
91     }
92     return 0;
93 }

View Code