POJ 3169 Layout (spfa+差分约束)

差分约束的解释：http://www.cnblogs.com/void/archive/2011/08/26/2153928.html

我也不是特别理解，要是给你a - b <= k 就建一条b->a权值为k的有向边，要是a - b >= k 就建一条a -> b边权是-k的有向边，要是让你求n到1的最大差，就是让你求1到n的最短距离。

差分约束系统有两种方式可以求解，最短路和最长路。当我们把不等式整理成d[a]+w<=d[b]时，我们求最长路。整理成d[a]+w>=d[b]时，我们求最短路。当求最短路时，我们通常要把各点距离初始化为正无穷，求最短路，把各点距离逐渐减小，直到符合所有不等式。也就是开始各点不符合条件，后来通过减小变得符合了，所以一定是符合条件的最大值。既然是求最大值，并且是减小各点距离，也就是把各点由数轴的右侧向左侧拉，所以我们一定要选择一个最终在数轴最左侧的点，并初始化为0，把所有正无穷的点拉近到符合不等式。最长路同理。(转来的)

题目就是让你求1到n的最短距离，要是有负环输出-1，要是d[n]没有更新就输出-2。

我用spfa做的，但是题目有个隐含的条件是D[i + 1] - D[i] >= 0。所以还要建i + 1到i上的0边。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <vector>
 5 #include <queue>
 6 using namespace std;
 7 const int MAXN = 1005;
 8 const int INF = 1e9;
 9 struct data {
10     int next , to , cost;
11 }edge[MAXN * MAXN];
12 int head[MAXN] , d[MAXN] , cont , cnt[MAXN];
13 bool vis[MAXN];
14 
15 void init(int n) {
16     for(int i = 0 ; i <= n ; i++) {
17         d[i] = INF;
18         head[i] = -1;
19         vis[i] = false;
20         cnt[i] = 0;
21     }
22     cont = 0;
23 }
24 
25 inline void add(int u , int v , int cost) {
26     edge[cont].next = head[u];
27     edge[cont].to = v;
28     edge[cont].cost = cost;
29     head[u] = cont++;
30 }
31 
32 bool spfa(int s , int n) {
33     d[s] = 0;
34     queue <int> que;
35     while(!que.empty()) {
36         que.pop();
37     }
38     que.push(s);
39     while(!que.empty()) {
40         int temp = que.front();
41         que.pop();
42         vis[temp] = false;
43         for(int i = head[temp] ; ~i ; i = edge[i].next) {
44             int v = edge[i].to;
45             if(d[v] > d[temp] + edge[i].cost) {
46                 d[v] = d[temp] + edge[i].cost;
47                 if(!vis[v]) {
48                     que.push(v);
49                     vis[v] = true;
50                 }
51                 cnt[v]++;
52                 if(cnt[v] >= n)
53                     return false;
54             }
55         }
56     }
57     return true;
58 }
59 
60 int main()
61 {
62     int n , m1 , m2 , u , v , w;
63     while(~scanf("%d %d %d" , &n , &m1 , &m2)) {
64         init(n);
65         while(m1--) {
66             scanf("%d %d %d" , &u , &v , &w);
67             add(u , v , w);
68         }
69         while(m2--) {
70             scanf("%d %d %d" , &u , &v , &w);
71             add(v , u , -w);
72         }
73         //隐含条件
74         for(int i = 1 ; i < n ; i++) {
75             add(i + 1 , i , 0);
76         }
77         if(spfa(1 , n)) {
78             if(d[n] >= INF)
79                 printf("-2
");
80             else
81                 printf("%d
" , d[n]);
82         }
83         else
84             printf("-1
");
85     }
86 }