這道題目（昂貴的聘禮）在poj上只有26%的ac率，貌似是第一道(總之是前幾道第一次引入的中文題目)，別以為中文題目就容易。中文題目就好理解，這題有25%的submit是因為理解錯誤而wa的。
言歸正傳...
題意給出幾個節(jié)點要求最短的路徑。
我建立的模型是這樣：括號中第一個表示錢，第二個是等級。
+-- 8000 --(1000, 2)-- 200---+
| |
(10000, 3) -+ +--(50, 2)
| |
+-- 5000 --(3000, 2)-- 200 --+
第一個反映當然是“單元最短路徑”dijkstra算法來做，但是WA了幾次后才發(fā)現(xiàn)原來我理解等級錯誤了。
如果A B C 的等級是 3 2 1， 而限制是1的話，那么從C -> A的路徑則視為非法。
繼續(xù)做，對路徑進行動態(tài)的記錄。結(jié)果居然出現(xiàn)某些點無法到達的情況，例如：
等級限制M = 1
+--5000--(1000, 2)--200---+
| |
(10000, 3) -+ +--([No.4] 200, 3)--50--([No.5] 50, 2)
| |
+--5000--(3000, 4)--100 --+
這種場景下，No.4節(jié)點由于dijkstra本身是一個貪心算法，所以會被下面的路徑標記。但是由于等級限制的限制No.5節(jié)點會被視為非法。而此題的正解應(yīng)該是走上面的路徑，將No.5節(jié)點納入計算節(jié)點中。
這時候就是說局部的最優(yōu)解不是最終的最優(yōu)解(是次優(yōu)解)，那么dijkstra算法就不能成立了。
那就不能用dijkstra了嗎？ 我看了看discus，很多人說用dp，用dfs等等...感覺很不甘心啊！
在憋了兩天之后，我終于找到了一個辦法。
直接用dijkstra肯定是不行的，如果對dijkstra做一些優(yōu)化，對每個目標節(jié)點做一次dijkstra的枚舉就可以避免次優(yōu)解的問題，如何來做呢？
dijkstra算法的時候，指定一個目標節(jié)點，也就是說循環(huán)計算該圖的dijkstra，每次都是from 0 to i節(jié)點。
這樣就能在一開始的時候得到0節(jié)點 和 目標節(jié)點能允許的等級范圍。以上圖為例，當枚舉到目標節(jié)點為No.5的時候，那么源節(jié)點的max_level = 3 + M = 4, min_level = 3 - 1 = 2，再計算No.5的等級限制為[1, 3]。將兩個等級merge一下，就是[2, 3]，也就是說從源節(jié)點所有到No.5節(jié)點的level必須在[2, 3]的范圍內(nèi)。
那么在dijkstra的時候，對于level = 4的節(jié)點就被視為非法，不進入計算中。
對dijkstra進行一些優(yōu)化，比如當計算到目標節(jié)點已知的時候就可以結(jié)束了。
還是要說這種的計算方法還是有優(yōu)化的空間，畢竟在計算No.5的時候會用到前面計算的結(jié)果，可以考慮dp，但是這題的數(shù)據(jù)較弱，ac之后就不想再弄了。
覺得上面雖然說了思路，還是給出代碼吧，這樣看得比較清楚，0ms ac。
1
#include <stdio.h>
2
3#define MAX_NODE 100
4#define MAX_D 100000000
5
6int M, N;
7
8struct _Node
9
{
10
int p;
11 int l;
12
}Node[MAX_NODE];
13
14int Engle[MAX_NODE][MAX_NODE] = {0};
15
16struct _Table
17{
18 int k;
19 int d;
20 int max_l;
21 int min_l;
22}Table[MAX_NODE];
23
24int result = MAX_D;
25
26void dijkstra(int t)
27{
28 int i, min_d, min_n;
29 int max_l, min_l;
30 // init
31 for (i = 0; i < N; ++i)
32
{
33 Table[i].k = 0;
34 Table[i].d = MAX_D;
35 Table[i].max_l = Node[i].l + M;
36 Table[i].min_l = Node[i].l - M;
37
}
38 Table[0].d = 0;
39 max_l = Table[0].max_l < Table[t].max_l ? Table[0].max_l : Table[t].max_l;
40 min_l = Table[0].min_l > Table[t].min_l ? Table[0].min_l : Table[t].min_l;
41 // dijkstra
42 while (!Table[t].k)
43 {
44 min_d = MAX_D;
45 min_n = -1;
46 // find min n;
47 for (i = 0; i < N; i++)
48 {
49 if (!Table[i].k && Table[i].d < min_d)
50 {
51 min_d = Table[i].d;
52 min_n = i;
53 }
54 }
55 // break
56 if (-1 == min_n)
57 break;
58 //
59 for (i = 0; i < N; ++i)
60 {
61 if ( min_l <= Node[i].l && Node[i].l <= max_l
62 && !Table[i].k
63 && Engle[min_n][i]
64 && Table[i].d > Engle[min_n][i] + Table[min_n].d)
65 {
66 Table[i].d = Engle[min_n][i] + Table[min_n].d;
67 }
68 }
69 //
70 Table[min_n].k = 1;
71 }
72
73 if (Table[t].k && result > Table[t].d + Node[t].p)
74 {
75 result = Table[t].d + Node[t].p;
76 }
77}
78
79
80
81void main()
82{
83 int P, L, X;
84 int T, V;
85 int i, n = 0;
86
87 scanf("%d %d", &M, &N);
88
89 while (EOF != scanf("%d %d %d", &P, &L, &X))
90 {
91 Node[n].l = L;
92 Node[n].p = P;
93 for (i = 0; i < X; ++i)
94 {
95 scanf("%d %d", &T, &V);
96 Engle[n][T - 1] = V;
97 }
98 n++;
99 }
100
101 for (i = 0; i < N; ++i)
102 {
103 dijkstra(i);
104 }
105 printf("%d\n", result);
106}
posted on 2011-05-14 00:16
margin 閱讀(486)
評論(0) 編輯 收藏 引用