ZOJ 2281 Way to Freedom

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



posted on 2008-02-08 21:29 杜仲当归 阅读(196) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

只有注册用户登录后才能发表评论。

导航

<2008年2月>
272829303112
3456789
10111213141516
17181920212223
2425262728291
2345678

统计

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜