poj 3169 Layout (差分约束)

题目连接：

题目大意：

　　在一个农场里，等待喂养的牛都按照自己的编号从1—>n排列，但是牛之间有一些特殊的关系，比如牛i与牛j相互讨厌（关系1），那么这两只牛之间最少间隔x，牛i与牛j相互喜欢（关系2），那么这两只牛之间最多间隔x。一共有n头牛，ml个关系2，有md个关系1。问：在满足这约束条件后，1到n的最大距离为多少，如果存在负环输出-1，不存在最长距离输出-2，否则输出最长距离。

解题思路：

　　典型的差分约束问题，但是这个比较麻烦的是，有最大约束还有最小约束。（dist[i]表示的从1到i的最长距离）

　　喜欢的关系存在：（i<j）dist[j] - dist[i] <= x。等价于：dist[j] <= dist[i] + x。

　　讨厌的关系存在：（i<j）dist[j] - dist[i] >= x。等价于：dist[i] <= dist[j] + x。

　　经过推导，可以看出用spfa求最短路即可，这道题目的关键在于建图。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 #include <vector>
 6 using namespace std;
 7 
 8 #define INF 0x3f3f3f3f
 9 #define maxn 1010
10 
11 struct Edge
12 {
13     int e, w;
14     Edge(int e=0, int w=0):e(e),w(w){}
15 };
16 
17 vector<Edge> G[maxn];
18 int dist[maxn];
19 void init ();
20 int spfa (int n);
21 
22 int main()
23 {
24     int n, ml, md;
25     while (scanf ("%d %d %d", &n, &ml, &md) != EOF)
26     {
27         init ();
28         int a, b, d;
29         while (ml --)
30         {
31             scanf ("%d %d %d", &a, &b, &d);
32             G[a].push_back(Edge(b, d));//对第二种关系正向建边
33         }
34         while (md --)
35         {
36             scanf ("%d %d %d", &a, &b, &d);
37             G[b].push_back(Edge(a, -d));//对第一种关系反向建边
38         }
39         printf ("%d
", spfa(n));
40     }
41     return 0;
42 }
43 void init ()
44 {
45     int i;
46     for (i=0; i<maxn; i++)
47     {
48         G[i].clear();
49         dist[i] = INF;
50     }
51 }
52 int spfa (int n)
53 {
54     int vis[maxn], updata[maxn];
55     queue<int>Q;
56     memset (vis, 0, sizeof(vis));
57     memset (updata, 0, sizeof(updata));
58     Q.push (1);
59     updata[1] = 1;
60     dist[1] = 0;
61     while (!Q.empty())
62     {
63         int p = Q.front();
64         Q.pop();
65         vis[p] = 0;
66         int len = G[p].size();
67 
68         for (int i=0; i<len; i++)
69         {
70             Edge q = G[p][i];
71             if (dist[q.e] > dist[p] + q.w)
72             {
73                 dist[q.e] = dist[p] + q.w;
74                 updata[q.e] ++;
75                 Q.push (q.e);
76                 vis[q.e] = true;
77                 if (updata[q.e] == n)
78                     return -1;//有负环
79             }
80         }
81     }
82     if (dist[n] == INF)
83         return -2;//无最长距离的路存在
84     return dist[n];
85 }

本文为博主原创文章，未经博主允许不得转载。