| layout | title | date | tags | |||
|---|---|---|---|---|---|---|
post |
[POJ] 3169 - Layout |
2012-02-26 |
|
題目網址：3169 - Layout
Farmer John 有 N 頭牛，這些牛站在一條直線上。這些牛皆有被編號（1 ~ N），他們會依照他們的編號順序排列。牛隻可以重疊，但能需要按照順序。
例：
- 全部的牛都在同一點 ⇒ 合法
- 牛1與牛2在同一點 ⇒ 合法
- 牛1與牛3在同一點，而牛2在牛3之後 ⇒ 不合法，牛2與牛3的順序沒按照編號。
這些牛就像人一樣，會有喜歡與討厭的情感。若兩頭牛互相喜歡，那麼他們排隊時，距離彼此必須小於等於給定的單位。若他們討厭彼此，則需要距離彼此大於等於給定的單位。要求求出這些牛排隊時最大的長度。
P.S. 牛與牛之間，喜歡與討厭都是雙向的！
- 牛隻數量 N，2 ≤ N ≤ 1,000
- 喜歡的牛隻對數 ML，1 ≤ ML ≤ 10,000
- 討厭的牛隻對數 MD，1 ≤ MD ≤ 10,000
- 距離 D，1 ≤ D ≤ 1,000,000
測試資料由三個整數開始 N ML MD，表示有 N 頭牛。接下來有 ML 行，每一行三個整數 A B D，表示 A 牛與 B 牛彼此喜歡，他們的距離要小於等於 D。接著再 MD 行，每一行三個整數 A B D，表示 A 牛與 B 牛彼此討厭，他們的距離要小於等於 D。
對於每一筆測試資料，輸出一個整數，最大的排隊長度。若不存在解時，輸出 -1。若存在無限多解時，輸出 -2。
標準的差分約束題型，若 A 牛與 B 牛互相喜歡，因此他們的距離需要小於等於 D，此時即可列出式子 xB - xA ≤ D。若 A 牛與 B 牛互相討厭，且需要距離大於等於 D，則可列出式子 xB - xA ≥ D。
在列完式子後，即可利用 Bellman-Ford 來求最短路徑。編號 1 的牛與編號 N 的牛的距離差即為答案。若出現負環，表示無解，輸出 -1。若到達編號 N 的牛的距離為無限大（即無法抵達），表示有任意解，輸出 -2。
<script src="https://gist.github.com/KuoE0/1950504.js"></script>Time Complexity: O(N × (ML + MD))
Source code on gist.