這道題目（昂貴的聘禮）在poj上只有26%的ac率，貌似是第一道(總之是前幾道第一次引入的中文題目)，別以為中文題目就容易。中文題目就好理解，這題有25%的submit是因?yàn)槔斫忮e(cuò)誤而wa的。
言歸正傳...
題意給出幾個(gè)節(jié)點(diǎn)要求最短的路徑。
我建立的模型是這樣：括號(hào)中第一個(gè)表示錢，第二個(gè)是等級(jí)。
+-- 8000 --(1000, 2)-- 200---+
| |
(10000, 3) -+ +--(50, 2)
| |
+-- 5000 --(3000, 2)-- 200 --+
第一個(gè)反映當(dāng)然是“單元最短路徑”dijkstra算法來(lái)做，但是WA了幾次后才發(fā)現(xiàn)原來(lái)我理解等級(jí)錯(cuò)誤了。
如果A B C 的等級(jí)是 3 2 1， 而限制是1的話，那么從C -> A的路徑則視為非法。
繼續(xù)做，對(duì)路徑進(jìn)行動(dòng)態(tài)的記錄。結(jié)果居然出現(xiàn)某些點(diǎn)無(wú)法到達(dá)的情況，例如：
等級(jí)限制M = 1
+--5000--(1000, 2)--200---+
| |
(10000, 3) -+ +--([No.4] 200, 3)--50--([No.5] 50, 2)
| |
+--5000--(3000, 4)--100 --+
這種場(chǎng)景下，No.4節(jié)點(diǎn)由于dijkstra本身是一個(gè)貪心算法，所以會(huì)被下面的路徑標(biāo)記。但是由于等級(jí)限制的限制No.5節(jié)點(diǎn)會(huì)被視為非法。而此題的正解應(yīng)該是走上面的路徑，將No.5節(jié)點(diǎn)納入計(jì)算節(jié)點(diǎn)中。
這時(shí)候就是說(shuō)局部的最優(yōu)解不是最終的最優(yōu)解(是次優(yōu)解)，那么dijkstra算法就不能成立了。
那就不能用dijkstra了嗎？ 我看了看discus，很多人說(shuō)用dp，用dfs等等...感覺(jué)很不甘心啊！
在憋了兩天之后，我終于找到了一個(gè)辦法。
直接用dijkstra肯定是不行的，如果對(duì)dijkstra做一些優(yōu)化，對(duì)每個(gè)目標(biāo)節(jié)點(diǎn)做一次dijkstra的枚舉就可以避免次優(yōu)解的問(wèn)題，如何來(lái)做呢？
dijkstra算法的時(shí)候，指定一個(gè)目標(biāo)節(jié)點(diǎn)，也就是說(shuō)循環(huán)計(jì)算該圖的dijkstra，每次都是from 0 to i節(jié)點(diǎn)。
這樣就能在一開(kāi)始的時(shí)候得到0節(jié)點(diǎn) 和 目標(biāo)節(jié)點(diǎn)能允許的等級(jí)范圍。以上圖為例，當(dāng)枚舉到目標(biāo)節(jié)點(diǎn)為No.5的時(shí)候，那么源節(jié)點(diǎn)的max_level = 3 + M = 4, min_level = 3 - 1 = 2，再計(jì)算No.5的等級(jí)限制為[1, 3]。將兩個(gè)等級(jí)merge一下，就是[2, 3]，也就是說(shuō)從源節(jié)點(diǎn)所有到No.5節(jié)點(diǎn)的level必須在[2, 3]的范圍內(nèi)。
那么在dijkstra的時(shí)候，對(duì)于level = 4的節(jié)點(diǎn)就被視為非法，不進(jìn)入計(jì)算中。
對(duì)dijkstra進(jìn)行一些優(yōu)化，比如當(dāng)計(jì)算到目標(biāo)節(jié)點(diǎn)已知的時(shí)候就可以結(jié)束了。
還是要說(shuō)這種的計(jì)算方法還是有優(yōu)化的空間，畢竟在計(jì)算No.5的時(shí)候會(huì)用到前面計(jì)算的結(jié)果，可以考慮dp，但是這題的數(shù)據(jù)較弱，ac之后就不想再弄了。
覺(jué)得上面雖然說(shuō)了思路，還是給出代碼吧，這樣看得比較清楚，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)
評(píng)論(0) 編輯 收藏 引用