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

　　最短路專題中的一道用到Bellman-Ford算法的題。

　　先簡單描述題目的意思：

　　兩個王國將開展一場星級戰爭，其中一個國家的防御系統被出賣，但是其中的信息有真有假?，F在給出某些防御塔間的位置關系，判斷是否有矛盾，有矛盾就是不可信，否則就是可信。其中有些是知道具體的相對位置，其余的知知道大概的相對方向，而且各個防御塔都是在南北向的一條直線上。

　　根據題意，就可以知道這是要判斷是否有矛盾的信息，換句話說就是要判斷是否有負權的回路。其中，較為簡單而且經典的方法就是Bellman Ford的算法。

　　根據《算法導論》描述：

　　這個算法能在一般的情況（存在負權邊的情況）下，解決單源最短路徑問題。對于給定的帶權有向圖G=(V, E)，其源點為s，加權函數為w：E→R，對該圖運行Bellman-Ford算法后可以返回一個布爾值，表明圖中是否存在一個從源點可達的權為負的回路。若存在這樣的回路的話，算法說明該問題無解；若不存在這樣的回路，算法將產生最短路徑及其權值。

For i:=1 to |V|-1 do For 每條邊(u,v)∈E doRelax(u,v,w); For每條邊(u,v)∈E doIf dis[u]+w<dis[v] Then Exit(False) http://www.nocow.cn/index.php?title=Bellman-Ford%E7%AE%97%E6%B3%95&oldid=8177#.E6.94.B9.E8.BF.9B.E5.92.8C.E4.BC.98.E5.8C.96 　　這個算法的時間復雜度是O(VE)，用于判斷是否有負權回路時，它還能稍作優化，我的代碼中已實現： View Code 1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #include<math.h>
5
6 #define Infp 0x7fffffff
7 #define Infn 0x80000000
8 #define DisCon 1000000000
9 #define MAX 999999999
10 #define MIN -999999999
11
12 #define Z(a) memset(a, 0, sizeof(a))
13 #define C(a, b) memcpy(a, b, sizeof(b))
14 #define Pi acos(-1)
15 #define FMAX (1E300)
16 #define FMIN (-1E300)
17 #define feq(a, b) (fabs((a)-(b))<1E-6)
18 #define flq(a, b) ((a)<(b)||feq(a, b))
19 #define RG 1005
20
21 struct Edge
22 {
23 int b;
24 int e;
25 int dis;
26 }e[200010];//簡單的記錄邊的信息
27
28 int bell(int en, int pn)
29 {
30 int dis[pn+1];
31 int chg;
32
33 dis[0]=0;
34 for(int i=1; i<=pn; i++)
35 dis[i]=DisCon;//這是為了防止溢出才不用最大值
36 for(int i=0; i<pn; i++)
37 {
38 chg=0;
39 for(int j=0; j<en; j++)
40 if(dis[e[j].e]>dis[e[j].b]+e[j].dis)//松弛操作
41 {
42 dis[e[j].e]=dis[e[j].b]+e[j].dis;
43 chg=1;//如果最終趨于穩定，就是說肯定沒有負權回路了
44 }
45 if(!chg)return 1;
46 /*************解釋*****************************
47 結合《算法導論》的解釋，如果從單源出發，而且圖是無負權回路的，
48 那么到任何一個短點的最短路徑最多只包含|V|-1條邊，而上述代碼最
49 外層的循環次數是|V|次，就是最多將構造含有|V|條邊的最短路集合。
50 假設循環不斷進行，一直有最短路被發現（也即一直有松弛的路徑更新
51 ），直到i>|V|而退出，這說明這時構造出了一條最短路是有多于|V|條
52 邊的，與初衷矛盾，所以這時說明了圖是有負權回路的！
53 *********************************************/
54 }
55 return 0;
56 }
57
58 int main()
59 {
60 int N, M;
61
62 while(scanf("%d%d", &N, &M)!=EOF)
63 {
64 int en=0;
65 while(M--)
66 {
67 getchar();
68
69 char c;
70 scanf("%c", &c);
71 if(c=='P')//具體的信息，雙向的邊都要構造
72 {
73 int a, b, dis;
74
75 scanf("%d%d%d", &a, &b, &dis);
76 e[en].b=a;
77 e[en].e=b;
78 e[en++].dis=dis;
79 e[en].b=b;
80 e[en].e=a;
81 e[en++].dis=-dis;
82 }
83 else//模糊的信息，據說邊長一定大于1，只構造單向的邊
84 {
85 int a, b;
86 scanf("%d%d", &a, &b);
87 e[en].b=b;
88 e[en].e=a;
89 e[en++].dis=-1;
90 }
91 }
92
93 if(bell(en, N))printf("Reliable\n");
94 else printf("Unreliable\n");
95 }
96
97 return 0;
98 }
UPD：
　　看了下差分約束做，結果反而不能1y了。。- -
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 #include <cstring> 5 6 using namespace std; 7 8 const int N = 1111; 9 const int M = 111111; 10 const int INF = 0x11111111; 11 struct Edge { 12 int u, v, c; 13 Edge() {} 14 Edge(int u, int v, int c) : u(u), v(v), c(c) {} 15 } edge[M << 1]; 16 int dis[N]; 17 18 bool bellman(int m) { 19 bool ok; 20 for (int i = 0; i < N; i++) dis[i] = INF; 21 for (int i = 0; i < N; i++) { 22 ok = true; 23 for (int j = 0; j < m; j++) { 24 if (dis[edge[j].v] > dis[edge[j].u] + edge[j].c) { 25 dis[edge[j].v] = dis[edge[j].u] + edge[j].c; 26 ok = false; 27 } 28 } 29 if (ok) return true; 30 } 31 return false; 32 } 33 34 int main() { 35 // freopen("in", "r", stdin); 36 int n, m; 37 int x, y, c; 38 char buf[3]; 39 while (~scanf("%d%d", &n, &m)) { 40 int cnt = 0; 41 for (int i = 0; i < m; i++) { 42 scanf("%s%d%d", buf, &x, &y); 43 if (buf[0] == 'P') { 44 scanf("%d", &c); 45 edge[cnt++] = Edge(x, y, c); 46 edge[cnt++] = Edge(y, x, -c); 47 } else edge[cnt++] = Edge(y, x, -1); 48 } 49 if (bellman(cnt)) puts("Reliable"); 50 else puts("Unreliable"); 51 } 52 return 0; 53 } View Code

?

——written by Lyon

轉載于:https://www.cnblogs.com/LyonLys/archive/2012/04/05/poj_2983_Lyon.html

總結

以上是生活随笔為你收集整理的poj 2983 Is the Information Reliable?的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。