学步园

无向图中给定单源，求到某点路径中最小权边的最大值。

可以将其看成求单源最短路径的变种，使用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        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