Bellman!?
有一個農夫的農場莫名奇妙出現了蟲洞，可以把自己傳送到過去時間的某個地方。 給定 F 張圖，每一張圖有 N 個區域（編號 1..N），有 M 條路，是雙向通行的，還有 W 個蟲洞，是單向通行的。 利用道路從一個區域到另一個區域需要耗時，而從蟲洞穿越則會回到過去時間的某個區域。 農夫想要從某個地方出發，遇到過去在起點的自己，請問他能不能成功呢？
第一行一個正整數 F ，代表有 F 個地圖。接下來有 F 筆測資。 每一筆測資第一行有三個整數: ，分別代表有 N 個區域、 M 條雙向路、 W 個蟲洞。 接下來有 M 行，每行有 三個數字，代表一條路從 S 到 E ，需要耗時 T 秒。 接下來有 W 行，每行也有 三個數字，代表一個蟲洞從 S 到 E ，穿越後會回到 T 秒前的時空。
對於每筆測資，可以成功輸出 YES ，無法達成輸出 NO ，輸出後換行。
標準的找負向環問題，類似 Bellman-Ford Algorithm。 不過還不是很清楚整個算法的思路，可能之後要再找時間研究。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
class Solution {
typedef struct{int from, to, cost;}EDGE;
private:
int F, N, M, W;
int ES;
int *dist;
EDGE *edge;
void link(int from, int to, int cost, int lev) {
--from; --to;
edge[lev].from=from;
edge[lev].to=to;
edge[lev].cost=cost;
}
void init(void) {
dist = new int[N+1];
edge = new EDGE[M*2+W+1];
ES=0;
}
void des(void) {
delete[] dist; delete[] edge;
ES=0;
}
void read_data() {
scanf("%d%d%d", &N,&M,&W);
init();
int u, v, w;
for(size_t i=0; i!=M; ++i) {
scanf("%d%d%d", &u, &v, &w);
link(u,v,w,ES);++ES;
link(v,u,w,ES);++ES;
}
for(size_t i=0; i!=W; ++i) {
scanf("%d%d%d", &u, &v, &w);
link(u,v,-w,ES);++ES;
}
}
bool find_negLoop(void) {
memset(dist, 0, sizeof(dist));
for(int i=0; i!=N; ++i) {
for(int j=0; j!=ES; ++j) {
EDGE inst=edge[j];
if( dist[inst.to] > dist[inst.from]+inst.cost) {
dist[inst.to] = dist[inst.from]+inst.cost;
if(i==N-1) return true;
}
}
}
return false;
}
public:
void solv(void) {
scanf("%d", &F);
while(F--) {
read_data();
printf(( find_negLoop() )?"YES\n":"NO\n");
//for(int i=0; i!=N; ++i) printf(" %d",dist[i]);
//puts("");
des();
}
}
};
int main(void) {
Solution sol;
sol.solv();
return 0;
}
先建立一個虛擬的節點 0 ，這個節點連接所有其他節點 1..N ，
用來當作起點，所以如果原本節點數是 V ，加上這個節點必須做 V 次 Relaxation，
當第 V+1 次還可以 Relax 時，代表偵測到負環。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct EDGE {
int from, to, cost;
EDGE(int from, int to, int cost):from(from),to(to),cost(cost) {}
};
vector< EDGE > edge;
int dist[510];
int N, M, W, T;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> T;
while(T--) {
cin >> N >> M >> W;
fill(dist, dist+510, 1e9);
dist[0] = 0;
edge.reserve(N+M*2+W);
for (int i=1; i<=N; ++i) edge.push_back( EDGE(0,i,0) );
for (int i=0; i<M; ++i) {
int s, t, c;
cin >> s >> t >> c;
edge.push_back( EDGE(s,t,c) );
edge.push_back( EDGE(t,s,c) );
}
for (int i=0; i<W; ++i) {
int s, t, c;
cin >> s >> t >> c;
edge.push_back( EDGE(s,t,-c) );
}
bool neg_ring=false;
for (int i=0; i<=N; ++i) {
for (int j=0; j<edge.size(); ++j) {
int new_d = dist[edge[j].from]+edge[j].cost;
if (new_d < dist[edge[j].to]) {
dist[edge[j].to] = new_d;
if (i==N) {
neg_ring=true;
i=j=1e9; // break
}
}
}
}
cout << (neg_ring?"YES":"NO") << endl;
edge.clear();
}
return 0;
}