| 2746723 |
2008-02-08 20:54:30 |
Accepted
|
2281
|
C++ |
00:01.51 |
25832K |
C.D.
|
无向图中给定单源，求到某点路径中最小权边的最大值。
可以将其看成求单源最短路径的变种，使用dijkstra算法+最大堆。
单源最短路径的算法是：记录从源点出发访问每一点i的最短路为value[i]，对于当前所有value中的最小值点u，进行BFS式的操作，对于每条Edge(u,v)，如果edge(u,v)+value[u] < value[v] 则更新v。
对此稍做修改。记录每条边目前能承受的最大重量为value[i]（即从源点所遍历路径的最小权中的最大值）。设u是当前结点，对于每条Edge(u,v)，当路径扩展到v时的最小value（min(edge, value[u])）大于value[v] 时更新。
由于边数目巨大(M<1000000)，因此使用链表储存。使用num数组保存起点为i的起始位置，next数组保存链表。num[i]=a,next[a]=b,next[b]=c,next[c]=d,next[d]=0，这里abcd都为边数组中的位置，表示以i为起点的边在abcd处。
WA了一下午，才发现把INF定义的太小了。
1
#include <cstdio>
2#include <string>
3
4#define min(x, y) ( x < y ? x : y )
5#define INF 2000000001
6
7int N, M, src, dst, size;
8const int MAXM = 1000010;
9const int MAXN = 100001;
10
11typedef struct
12
{
13
int y, w;
14
} Edge;
15Edge e[MAXM * 2];
16int next[MAXM * 2], value[MAXN], visited[MAXN], num[MAXN], heap[MAXN], idx[MAXN];
17//heap存放点序号，idx存放点在heap中的位置
18
19int init ();
20int dijk ();
21int get_top ();
22void update ( int );
23void print_heap ();
24void print_value ();
25void print_link ();
26
27int main ()
28{
29 //freopen ( "in.txt", "r", stdin );
30 while ( init () )
31
{
32 printf ( "%d\n", dijk () );
33
}
34 return 0;
35}
36
37int init ()
38{
39 if ( scanf ( "%d%d", &N, &M ) != 2 )
40 {
41 return 0;
42 }
43 int i, j;
44 memset ( num, 0x00, sizeof ( num ) );
45 for ( i = 1, j = 0; i <= M; i ++ )
46 {
47 int tx, ty, tw;
48 scanf ( "%d%d%d", &tx, &ty, &tw );
49 e[++ j].w = tw, e[j].y = ty, next[j] = num[tx], num[tx] = j;
50 e[++ j].w = tw, e[j].y = tx, next[j] = num[ty], num[ty] = j;
51 }
52 scanf ( "%d%d", &src, &dst );
53 memset ( value, 0, sizeof ( value ) );
54 memset ( visited, 0, sizeof ( visited ) );
55 memset ( idx, 0, sizeof ( idx ) );
56 return 1;
57}
58
59int dijk ()
60{
61 size = 0;
62 value[src] = INF, visited[src] = 1;
63 heap[++ size] = src, idx[src] = 1;
64 while ( true )
65 {
66 if ( visited[dst] || size == 0 )
67 {
68 break;
69 }
70 int j, u, v;
71 u = get_top ();
72 visited[u] = 1;
73 for ( j = num[u]; j; j = next[j] )
74 {
75 v = e[j].y;
76 if ( !visited[v] && value[v] < min ( value[u], e[j].w ) )
77 {
78 if ( idx[v] == 0 )
79 {
80 heap[++ size] = v;
81 idx[v] = size;
82 }
83 value[v] = min ( value[u], e[j].w );
84 update ( v );
85 }
86 }
87 }
88 return value[dst];
89}
90
91int get_top ()
92{
93 int res = heap[1], p = 1, q = 2, r = heap[size --];
94 while ( q <= size )
95 {
96 if ( q < size && value[heap[q + 1]] > value[heap[q]] )
97 {
98 q ++;
99 }
100 if ( value[heap[q]] > value[r] )
101 {
102 idx[heap[q]] = p;
103 heap[p] = heap[q];
104 p = q; q = p << 1;
105 }
106 else
107 {
108 break;
109 }
110 }
111 heap[p] = r; idx[r] = p;
112 return res;
113}
114
115void update ( int r )
116{
117 int q = idx[r], p = q >> 1;
118 while ( p && value[heap[p]] < value[r] )
119 {
120 idx[heap[p]] = q; heap[q] = heap[p];
121 q = p; p = q >> 1;
122 }
123 heap[q] = r; idx[r] = q;
124}
125
126