分享到plurk 分享到twitter 分享到facebook

版本 1aff6aac5a286f596328a6cfb5b99e14016c837b

題解樣板

網址

http://poj.org/problem?id=3169

題意

Farmer John 有 N 頭牛,這些牛站在一條直線上。這些牛皆有被編號(1 ~ N),他們會依照他們的編號順序排列。牛隻可以重疊,但能需要按照順序。

例:

全部的牛都在同一點 -> 合法 牛1與牛2在同一點 -> 合法
牛1與牛3在同一點,而牛2在牛3之後 -> 不合法,牛2與牛3的順序沒按照編號。

這些牛就像人一樣,會有喜歡與討厭的情感。若兩頭牛互相喜歡,那麼他們排隊時,距離彼此必須小於等於給定的單位。若他們討厭彼此,則需要距離彼此大於等於給定的單位。要求求出這些牛排隊時最大的長度。

P.S. 牛與牛之間,喜歡與討厭都是雙向的!

Technique details

-  牛隻數量 **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。

Time Complexity: O( N × (ML + MD ) )