POJ

Layout

差分约束：

形如：$x1-x2>=a，x1-x3>=b，x2-x3<=c$

出现这样式子便要用到差分约束加最短路了。当要求$x1与x3$的最大差值时要用到最短路，所有的式子要转换成$x1-x2<=a$的形式，当求最小值时用最长路，所有式子转换为$x1-x2>=a$的形式。至于建图则需要根据题意确定边的方向。

原题链接：http://poj.org/problem?id=3169

题目大意：

n头牛，从1到n排序，每头牛按照序号在一条直线排队，允许一个位置有多头牛，有些牛有喜欢的或不喜欢的牛，所以对彼此之间的距离有要求，要求出第1头牛与第n头牛之间的最大距离。

解题思路：

求最大距离，用最短路，存在负值，也就有可能有负环，用spfa。因为要判断能不能排队，所以要建一个超级源点，连接所有的牛，并经过所有的边。

代码：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <vector>
 5 #include <queue>
 6 using namespace std;
 7 typedef long long ll;
 8 #define debug(a) cout<<#a<<":"<<a<<endl;
 9 const int INF=0x3f3f3f3f;
10 const int N=1e6+7;
11 const int mod=1e9+7;
12 int maxn,minn;
13 int T,n;
14 int u,v,w;
15 int dis[N];
16 int vis[N];
17 int cnt[N];
18 struct aa{
19     int u,w;
20 }p;
21 vector<aa>mp[N];
22 bool spfa(int a){
23     memset(vis,0,sizeof(vis));
24     memset(dis,INF,sizeof(dis));
25     memset(cnt,0,sizeof(cnt));
26     queue<int>que;
27     que.push(a);
28     dis[a]=0;
29     while(!que.empty()){
30         int a=que.front();
31         vis[a]=0;
32         que.pop();
33         for(int i=0;i<mp[a].size();i++){
34             p=mp[a][i];
35             if(dis[p.u]>dis[a]+p.w){
36                 dis[p.u]=dis[a]+p.w;
37                 cnt[p.u]=cnt[a]+1;
38                 if(cnt[p.u]>=n){
39                     return true;
40                 }
41                 if(vis[p.u]==0){
42                     que.push(p.u);
43                     vis[p.u]=1;
44                 }
45             }
46         }
47     }
48     return false;
49 }
50 int main(){
51     int m1,m2;
52     cin>>n>>m1>>m2;
53     for(int i=1;i<=m1;i++){
54         cin>>u>>v>>w;
55         p.u=v;
56         p.w=w;
57         mp[u].push_back(p);
58     }
59     for(int i=1;i<=m2;i++){
60         cin>>u>>v>>w;
61         p.w=-w;
62         p.u=u;
63         mp[v].push_back(p);
64     }
65     for(int i=1;i<n;i++){
66         p.u=i;
67         p.w=0;
68         mp[i+1].push_back(p);
69     } 
70     if(spfa(n)){
71         puts("-1");
72     }
73     else{
74         spfa(1);
75         if(dis[n]>=INF/2){
76             puts("-2");
77         }
78         else{
79             printf("%d
",dis[n]);
80         }
81     }
82     return 0;
83 }