无向图中给定单源，求到某点路径中最小权边的最大值。可以将其看成求单源最短路径的变种，使用dijkstra算法+最大堆。单源最短路径的算法是：记录从源点出发访问每一点i的最短路为value[i]，对于当前所有value中的最小值点u，进行BFS式的操作，对于每条Edge(u,v)，如果edge(u,v)+value[u] < value[v] 则更新v。这是一个贪心的算法，可以证明每次出队列的u最优。 本题求的是最大单边，对此稍做修改。记录每条边目前能承受的最大重量为value[i]（即从源点所遍历路径的最小权中的最大值）。设u是当前结点，对于每条Edge(u,v)，当路径扩展到v时的最小value（min(edge, value[u])）——即路径的最短边——大于value[v] 时更新。在联通图内，每一次要求的路径都是最大，因此在BFS的过程中，边是从大到小排列，对于当前所有value中的最大值点u进行操作。因为点的数目巨大，遍历需要N<100000，可以用堆存放value。实际程序里堆存放的是点的index，使用一个辅助数组来存放index在heap中的位置，如heap[1] = 6, idx[6] = 1。为了编程方便，heap以1开始。由于边数目巨大(M<1000000)，因此使用链表储存。使用num数组保存起点为i的起始位置，next数组保存链表。num[i]=a,next[a]=b,next[b]=c,next[c]=d,next[d]=0，这里abcd都为边数组中的位置，表示以i为起点的边终点为abcd。 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 else107 {108 break;109 }110 }111 heap[p] = r; idx[r] = p;112 return res;113}114115void 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}125126
评论