POJ3169(最短路+差分約束)
Layout
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 7613
Accepted: 3658
Description
Like everyone else, cows like to stand close to their friends when queuing for feed. FJ has N (2 <= N <= 1,000) cows numbered 1..N standing along a straight line waiting for feed. The cows are standing in the same order as they are numbered, and since they
can be rather pushy, it is possible that two or more cows can line up at exactly the same location (that is, if we think of each cow as being located at some coordinate on a number line, then it is possible for two or more cows to share the same coordinate).
Some cows like each other and want to be within a certain distance of each other in line. Some really dislike each other and want to be separated by at least a certain distance. A list of ML (1 <= ML <= 10,000) constraints describes which cows like each other
and the maximum distance by which they may be separated; a subsequent list of MD constraints (1 <= MD <= 10,000) tells which cows dislike each other and the minimum distance by which they must be separated.
Your job is to compute, if possible, the maximum possible distance between cow 1 and cow N that satisfies the distance constraints.
Input
Line 1: Three space-separated integers: N, ML, and MD.
Lines 2..ML+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at most D (1 <= D <= 1,000,000) apart.
Lines ML+2..ML+MD+1: Each line contains three space-separated positive integers: A, B, and D, with 1 <= A < B <= N. Cows A and B must be at least D (1 <= D <= 1,000,000) apart.
Output
Line 1: A single integer. If no line-up is possible, output -1. If cows 1 and N can be arbitrarily far apart, output -2. Otherwise output the greatest possible distance between cows 1 and N.
Sample Input
4 2 1
1 3 10
2 4 20
2 3 3
Sample Output
27
Hint
Explanation of the sample:
There are 4 cows. Cows #1 and #3 must be no more than 10 units apart, cows #2 and #4 must be no more than 20 units apart, and cows #2 and #3 dislike each other and must be no fewer than 3 units apart.
The best layout, in terms of coordinates on a number line, is to put cow #1 at 0, cow #2 at 7, cow #3 at 10, and cow #4 at 27.
Source
USACO 2005 December Gold
題意：一個牛捨裡有N頭牛，有一些牛的關系比較好，他們希望彼此不超過一定的距離。當然也有些牛關系不好，他們希望彼此超過一定的距離。有ML對牛的關系比較好，並給出每對牛的所不超過的距離D；同樣，有MD對牛的關系不好，並給出每對牛的所超過的距離D。問是否有滿足這樣的安排方案滿足所有牛的要求。若不存在，輸出-1；若存在，但是牛1和牛N之間的距離可以任意大，輸出-2；否則，輸出牛1和牛N之間的最大距離。
解析：記第i號牛的位置是d[i]，首先，牛市按照編號順序排的，所以有d[i] <= d[i+1]成立。其次，對於關系好的牛的最大距離限制有d[AL] + DL >= d[BL]，同樣對於關系不好的牛的最小距離限制有d[AD] + DD <= d[BD]。這樣，原來的問題就可以轉化為在滿足著三個不等式組的情況下，求解d[N] - d[1]的最大值問題。當然可以用線性規劃的方法去解決。但是這道題還可以更簡單的求解。這個可以抽象為一個無向圖，各個牛為頂點，他們之間的好或不好的關系為邊，限制的距離作為邊尚德權值。這樣可以將這三個不等式轉化一下：d[i+1]
+ 0 >= d[i]表示從i+1到i連一條權值為0的邊，d[AL] + DL >= d[BL]表示從AL到BL連一條權值為DL的邊，d[BD] - DD >= d[AD]表示從BD到AD連一條權值為-DD的邊。所求d[N] - d[1]的最大值，對應於d[1]到d[n]之間的最短路徑。由於存在負權邊，所以用bellman-ford算法。
#include
#include
#include
#include
#include
#include
#include
#include
