这道题目（昂贵的聘礼）在poj上只有26%的ac率，貌似是第一道(总之是前几道第一次引入的中文题目)，别以为中文题目就容易。中文题目就好理解，这题有25%的submit是因为理解错误而wa的。
言归正传...
题意给出几个节点要求最短的路径。
我建立的模型是这样：括号中第一个表示钱，第二个是等级。
+-- 8000 --(1000, 2)-- 200---+
| |
(10000, 3) -+ +--(50, 2)
| |
+-- 5000 --(3000, 2)-- 200 --+
第一个反映当然是“单元最短路径”dijkstra算法来做，但是WA了几次后才发现原来我理解等级错误了。
如果A B C 的等级是 3 2 1， 而限制是1的话，那么从C -> A的路径则视为非法。
继续做，对路径进行动态的记录。结果居然出现某些点无法到达的情况，例如：
等级限制M = 1
+--5000--(1000, 2)--200---+
| |
(10000, 3) -+ +--([No.4] 200, 3)--50--([No.5] 50, 2)
| |
+--5000--(3000, 4)--100 --+
这种场景下，No.4节点由于dijkstra本身是一个贪心算法，所以会被下面的路径标记。但是由于等级限制的限制No.5节点会被视为非法。而此题的正解应该是走上面的路径，将No.5节点纳入计算节点中。
这时候就是说局部的最优解不是最终的最优解(是次优解)，那么dijkstra算法就不能成立了。
那就不能用dijkstra了吗？ 我看了看discus，很多人说用dp，用dfs等等...感觉很不甘心啊！
在憋了两天之后，我终于找到了一个办法。
直接用dijkstra肯定是不行的，如果对dijkstra做一些优化，对每个目标节点做一次dijkstra的枚举就可以避免次优解的问题，如何来做呢？
dijkstra算法的时候，指定一个目标节点，也就是说循环计算该图的dijkstra，每次都是from 0 to i节点。
这样就能在一开始的时候得到0节点 和 目标节点能允许的等级范围。以上图为例，当枚举到目标节点为No.5的时候，那么源节点的max_level = 3 + M = 4, min_level = 3 - 1 = 2，再计算No.5的等级限制为[1, 3]。将两个等级merge一下，就是[2, 3]，也就是说从源节点所有到No.5节点的level必须在[2, 3]的范围内。
那么在dijkstra的时候，对于level = 4的节点就被视为非法，不进入计算中。
对dijkstra进行一些优化，比如当计算到目标节点已知的时候就可以结束了。
还是要说这种的计算方法还是有优化的空间，毕竟在计算No.5的时候会用到前面计算的结果，可以考虑dp，但是这题的数据较弱，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 阅读(447)
评论(0) 编辑 收藏 引用