POJ 3169 Layout （spfa+差分约束）

题目大意：n头牛，按编号1~n从左往右排列，可以多头牛站在同一个点，给出ml行条件，每行三个数a b c表示dis[b]-dis[a]<=c，接下来有md行条件，每行三个数a b c，表示dis[b]-dis[a]>=c。求出出第一头牛和第n头牛的最大可能距离。若不可能把所有牛排成一排即条件有矛盾，则输出“-1”，若第一头牛和第n头牛的距离可以无限大，则输出“-2”。

解题思路：第二道差分约束的题目。根据题目给出的三个约束条件：

　　　　　①dis[B]-dis[A]<=C

　　　　　②dis[B]-dis[A]>=C → dis[A]-dis[B]<=-C

　　　　　③dis[A]-dis[B]<=0

建图，然后同样的，因为要使距离尽可能大，所以if(dis[i]-dis[k]>cost[k][i]) dis[i]=dis[k]+cost[k][i]。

当出现负环，则说明该图矛盾，输出“-1”，当dis[n]==INF说明1和n之间距离可以无穷大，输出“-2”，其他时候输出dis[n]-dis[1]。

代码：

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 const int N=1e3+5;
 8 const int INF=0x3f3f3f3f;
 9 const int MAXN=3e4+5;
10 
11 struct node{
12     int to,w,next;
13 }edge[MAXN];
14 
15 int n,idx;
16 int head[N],dis[N],qcnt[N];
17 bool vis[N];
18 
19 void init(){
20     idx=1;
21     memset(head,-1,sizeof(head));
22 }
23 
24 void addedge(int u,int v,int w){
25     edge[idx].w=w;
26     edge[idx].to=v;
27     edge[idx].next=head[u];
28     head[u]=idx;
29     idx++;
30 }
31 
32 bool spfa(int s) {
33     memset(dis,0x3f,sizeof(dis));
34     dis[s]=0;
35     queue<int>q;
36     q.push(s);
37     while(!q.empty()){
38         int k=q.front();
39         q.pop();
40         vis[k]=false;
41         for(int i=head[k];i!=-1;i=edge[i].next){
42             node t=edge[i];
43             if(dis[k]+t.w<dis[t.to]){
44                 dis[t.to]=dis[k]+t.w;
45                 if(!vis[t.to]){
46                     q.push(t.to);
47                     qcnt[t.to]++;
48                     if(qcnt[t.to]>=n)
49                         return false;
50                     vis[t.to]=true;
51                 }
52             }
53         }
54     }
55     return true;
56 }
57 
58 int main(){
59     init();
60     int ml,md;
61     scanf("%d%d%d",&n,&ml,&md);
62     int a,b,c;
63     for(int i=1;i<=ml;i++){
64         scanf("%d%d%d",&a,&b,&c);
65         addedge(a,b,c);            //b-a<=c 
66     }
67     for(int i=1;i<=md;i++){
68         scanf("%d%d%d",&a,&b,&c);
69         addedge(b,a,-c);        //b-a>=c → a-b<=-c都改成小于的形式 
70     }
71     for(int i=1;i<=n-1;i++){
72         addedge(i+1,i,0);        //默认的dis[i+1]-dis[i]>=0
73     }
74     if(!spfa(1))
75         puts("-1");
76     else if(dis[n]==INF)
77         puts("-2");
78     else
79         printf("%d
",dis[n]-dis[1]);
80     return 0;
81 }