POJ3169(差分约束)

题意：有N头牛，这些牛都拥有一个属性x表示其在坐标轴上的坐标。现在给定ML组约束条件表示A、B两头牛坐标之差不能够超过C；MD组约束条件表示A、B两头牛坐标之差不能小于C，现在问1和N号牛之间最长的距离为多大，如果存在则输出最大长度，如果任意输出-2，如果已知条件存在矛盾输出-1。

拿样例来分析

4 2 1
1 3 10
2 4 20
2 3 3
S3 - S1 <= 10     InsertEdge(u,v,w);
S4 - S2 <= 20     InsertEdge(u,v,w);
S3 - S2 >= 3   ==> S2 - S3 <= -3   InsertEdge(v,u,-w);
隐含条件：前一头牛一定在后一头牛前面或者相等的位置 
S(i-1) - Si <= 0     for(int i=1; i<=n; i++)    InsertEdge(i,i-1,0);
最后要求的是 Sn - S1 <= M ，求这个M的值

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <queue>
 7 using namespace std;
 8 #define inf 9999999
 9 #define N 1024
10 #define M 40000
11 int dis[N],vis[N],head[N],in[N];
12 int size,n,m1,m2;
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 void Init()
20 {
21     size = 0;
22     memset(head,-1,sizeof(head));
23 }
24 void InsertEdge(int u,int v,int w)
25 {
26     edge[size] = Edge(v,w,head[u]);
27     head[u] = size++;
28 }
29 bool spfa()
30 {
31     for(int i=0; i<=n; i++)
32     {
33         vis[i] = 0; dis[i] = inf ; in[i] = 0;
34     }
35     queue<int> Q;
36     while(!Q.empty()) Q.pop();
37     vis[1] = 1 ; dis[1] = 0 ; in[1] = 1;
38     Q.push(1);
39     while(!Q.empty())
40     {
41         int u = Q.front();
42         Q.pop();
43         vis[u] = 0;
44         for(int i=head[u] ; i!=-1 ; i=edge[i].next)
45         {
46             int v =edge[i].v;
47             if(dis[v] > dis[u] + edge[i].w)
48             {
49                 dis[v] = dis[u] + edge[i].w;
50                 if(!vis[v])
51                 {
52                     vis[v] = 1;
53                     in[v]++;
54                     if(in[v]>(n+1)) return 0;
55                     Q.push(v);
56                 }
57             }
58         }
59     }
60     return 1;
61 }
62 int main()
63 {
64     while(scanf("%d%d%d",&n,&m1,&m2)!=EOF)
65     {
66         Init();
67         int u,v,w;
68         for(int i=1; i<=m1; i++)
69         {
70             scanf("%d%d%d",&u,&v,&w);
71             InsertEdge(u,v,w);
72         }
73         for(int i=1; i<=m2; i++)
74         {
75             scanf("%d%d%d",&u,&v,&w);
76             InsertEdge(v,u,-w);
77         }
78         for(int i=1; i<=n; i++)
79         InsertEdge(i,i-1,0);
80         if(!spfa()) printf("-1
");
81         else 
82         {
83             if(dis[n]==inf) printf("-2
");
84             else printf("%d
",dis[n]);
85         }
86     }
87     return 0;
88 }

View Code