Feb 26, 2012
題目網址：3169 - Layout
題目概述
Farmer John 有 N 頭牛，這些牛站在一條直線上。這些牛皆有被編號（1 ~ N），他們會依照他們的編號順序排列。牛隻可以重疊，但能需要按照順序。
例：
- 全部的牛都在同一點 ⇒ 合法
- 牛1與牛2在同一點 ⇒ 合法
- 牛1與牛3在同一點，而牛2在牛3之後 ⇒ 不合法，牛2與牛3的順序沒按照編號。
這些牛就像人一樣，會有喜歡與討厭的情感。若兩頭牛互相喜歡，那麼他們排隊時，距離彼此必須小於等於給定的單位。若他們討厭彼此，則需要距離彼此大於等於給定的單位。要求求出這些牛排隊時最大的長度。
P.S. 牛與牛之間，喜歡與討厭都是雙向的！
Technique Detail
- 牛隻數量 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))
Source Code
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <queue> | |
| using namespace std; | |
| #define MAXN 1010 | |
| struct EDGE { | |
| int v, w, next; | |
| }; | |
| EDGE edge[ 3000010 ]; | |
| int adj[ MAXN ], dis[ MAXN ], cnt[ MAXN ]; | |
| bool inque[ MAXN ]; | |
| int n, e1, e2, total; | |
| queue< int > que; | |
| void addEdge( int a, int b, int w ) { | |
| edge[ total ].v = b, edge[ total ].w = w, edge[ total ].next = adj[ a ]; | |
| adj[ a ] = total; | |
| ++total; | |
| } | |
| int SPFA( int sr ) { | |
| int now, next, i; | |
| memset( dis, 63, sizeof( dis ) ); | |
| memset( cnt, 0, sizeof( cnt ) ); | |
| while ( !que.empty() ) | |
| que.pop(); | |
| dis[ sr ] = 0; | |
| inque[ sr ] = 1, cnt[ sr ] = n; | |
| que.push( sr ); | |
| while ( !que.empty() ) { | |
| now = que.front(); | |
| que.pop(); | |
| inque[ now ] = 0; | |
| for ( i = adj[ now ]; i != -1; i = edge[ i ].next ) { | |
| EDGE temp = edge[ i ]; | |
| next = edge[ i ].v; | |
| if ( dis[ now ] + edge[ i ].w < dis[ next ] ) { | |
| dis[ next ] = dis[ now ] + edge[ i ].w; | |
| if ( !inque[ next ] ) { | |
| ++cnt[ next ]; | |
| if ( cnt[ next ] > n ) | |
| return -1; | |
| que.push( next ); | |
| inque[ next ] = 1; | |
| } | |
| } | |
| } | |
| } | |
| return dis[ n ] != dis[ 0 ] ? dis[ n ] : -2; | |
| } | |
| int main() { | |
| int i, a, b, w; | |
| while ( ~scanf( "%d %d %d", &n, &e1, &e2 ) ) { | |
| total = 0; | |
| memset( adj, -1, sizeof( adj ) ); | |
| for ( i = 0; i < e1; ++i ) { | |
| scanf( "%d %d %d", &a, &b, &w ); | |
| addEdge( a, b, w ); | |
| } | |
| for ( i = 0; i < e2; ++i ) { | |
| scanf( "%d %d %d", &a, &b, &w ); | |
| addEdge( b, a, -w ); | |
| } | |
| printf( "%d\n", SPFA( 1 ) ); | |
| } | |
| return 0; | |
| } | |
Source code on gist.