poj 3169 Layout

题意：

n头牛编号为1到n，按照编号的顺序排成一列，每两头牛的之间的距离 >= 0。这些牛的距离存在着一些约束关系：1.有ml组（u, v, w）的约束关系，表示牛[u]和牛[v]之间的距离必须 <= w。2.有md组（u, v, w）的约束关系，表示牛[u]和牛[v]之间的距离必须 >= w。问如果这n头无法排成队伍，则输出-1，如果牛[1]和牛[n]的距离可以无限远，则输出-2，否则则输出牛[1]和牛[n]之间的最大距离。

分析：

三个式子：

1、s[i+1]-s[i]>=0 ==> s[i]-s[i+1]<=0

2、ML 时：s[end]-s[st]<=x

3、MD 时: s[end]-s[st]>=x ==> s[st]-s[end]<=-x

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 #define inf 100000000
 9 struct Edge
10 {
11     int s,e;
12     int val;
13 }edge[25000];
14 
15 int pe;
16 int N,ML,MD;
17 int dis[1100];
18 
19 bool bellman_ford()
20 {
21     bool sign;
22 
23     for(int j=0;j<N+1;j++)
24     {
25         sign=false;
26         for(int i=0;i<pe;i++)
27             if(dis[edge[i].e] > dis[edge[i].s] + edge[i].val)
28             {
29                 dis[edge[i].e] = dis[edge[i].s] + edge[i].val;
30                 sign=true;
31             }
32         if(!sign)
33             break;
34     }
35     if(sign)
36         return false;//存在负环
37     else
38         return true;
39 }
40 
41 int main()
42 {
43     while(scanf("%d%d%d",&N,&ML,&MD) !=EOF)
44     {
45         for(int i=0;i<1100;i++)
46             dis[i]=inf;
47         dis[0]=0;
48         dis[1]=0;
49         pe=0;
50 
51         int a,b,x;
52         for(int i=1;i<=N-1;i++)
53         {
54             edge[pe].s=i+1;
55             edge[pe].e=i;
56             edge[pe++].val=0;
57         }
58         for(int i=0;i<ML;i++)
59         {
60             scanf("%d%d%d",&a,&b,&x);
61             edge[pe].s=a;
62             edge[pe].e=b;
63             edge[pe++].val=x;
64         }
65         for(int i=0;i<MD;i++)
66         {
67             scanf("%d%d%d",&a,&b,&x);
68             edge[pe].s=b;
69             edge[pe].e=a;
70             edge[pe++].val=-x;
71         }
72     
73         if(bellman_ford() && dis[N] != inf)
74             printf("%d\n",dis[N]);
75         else if(dis[N] == inf)
76             puts("-2");
77         else
78             puts("-1");
79     }
80     return 0;
81 }