来更新一下自己的帖子

今天是 2008.5.19 全国哀悼日，先为遇难的同胞默哀3分钟。

以POJ3195 - Candies做练习实现Dijkstra，题目如下：

POJ3159 - Candies
Time Limit: 1500MS        Memory Limit: 131072K

Description

During the kindergarten days, flymouse was the monitor of his class. Occasionally the head-teacher brought the kids of 
flymouse's class a large bag of candies and had flymouse distribute them. All the kids loved candies very much and often 
compared the numbers of candies they got with others. A kid A could had the idea that though it might be the case that 
another kid B was better than him in some aspect and therefore had a reason for deserving more candies than he did, he 
should never get a certain number of candies fewer than B did no matter how many candies he actually got, otherwise he 
would feel dissatisfied and go to the head-teacher to complain about flymouse's biased distribution.

snoopy shared class with flymouse at that time. flymouse always compared the number of his candies with that of snoopy's. 
He wanted to make the difference between the numbers as large as possible while keeping every kid satisfied. Now he had 
just got another bag of candies from the head-teacher, what was the largest difference he could make out of it?

Input

The input contains a single test cases. The test cases starts with a line with two integers N and M not exceeding 30 000 
and 150 000 respectively. N is the number of kids in the class and the kids were numbered 1 through N. snoopy and flymouse 
were always numbered 1 and N. Then follow M lines each holding three integers A, B and c in order, meaning that kid A believed 
that kid B should never get over c candies more than he did.

Output

Output one line with only the largest difference desired. The difference is guaranteed to be finite.

Sample Input

2 2
1 2 5
2 1 4

Sample Output

5

Hint
32-bit signed integer type is capable of doing all arithmetic.

Source
POJ Monthly--2006.12.31, Sempr

第一次尝试用stl来写，复杂度O( |E|log|E| )，结果tle了，郁闷。

第二次自己写个二叉堆实现。

用二叉堆有两种实现方法：

一种是将所有点的dist都初始化为无穷放在堆中，如果需要更新，做一个Decrease。
引用Weiss书中的一句话：如果重要的是知道元素在什么地方，那么除堆之外，还必须用到诸如散列表都其他的数据结构。做Decrease需要知道点在堆中的位置，那么必须维护一个散列表来实现。这种方法复杂度是 O( |E|log|V| )。

另外一种是只将起点放入堆中，如果某个点的dist需要更新，做Insert。这样堆中会有重复的点，出堆时需要验证一下该点是否被访问过。复杂度为O( |E|log|E| )

下面是我写的第一种实现的代码（这次偷懒没注释 -_-+ ），依然是ANSI C实现

#include <stdio.h>

#define INF  (0x7FfFfFfF)
#define MAXE (150005)
#define MAXV (30005)

struct edge
{
    int vertex, weight;
    struct edge *next;
} pool[MAXE], *e = pool, *adj[MAXV];

short position[MAXV] = { 0, 1 }, heap[MAXV<<1] = { 1, 1 }, *top = heap+1;
int dist[MAXV] = { INF, 0 }, size, N, M;
char marked[MAXV];

void Input( void );
void Init( void );
void Solve( void );
void Output( void );

void DeleteMin( void );
void Decrease( int i );

int main( void )
{
    Input();
    Init();
    Solve();
    Output();    
    return 0;
}

void Input( void )
{
    int i, j, k, temp;
    scanf( "%d %d", &N, &M );
    getchar();
    while ( M-- )
    {
        i = 0;
        while ( ' ' != ( temp = getchar() ) )
        {
            i *= 10;
            i += ( temp & 0xf );
        }
        j = 0;
        while ( ' ' != ( temp = getchar() ) )
        {
            j *= 10;
            j += ( temp & 0xf );
        }
        k = 0;
        while ( '\n' != ( temp = getchar() ) )
        {
            k *= 10;
            k += ( temp & 0xf );
        }        
        e->vertex = j;
        e->weight = k;
        e->next = adj[i];
        adj[i] = e++;
    }
    return;
}

void Init( void )
{
    int i;
    size = N;
    for ( i = 2; i <= N; ++i )
    {
        heap[i] = position[i] = i;
        dist[i] = INF;
    }
    return;
}

void Solve( void )
{
    int d, v, temp;
    while ( *top != N )
    {
        marked[*top] = 1;
        e = adj[*top];
        d = dist[*top];
        DeleteMin();    
        for ( NULL; e; e = e->next )
        {            
            if ( !marked[e->vertex] )
            {
                v = e->vertex;
                temp = d + e->weight;
                if ( temp < dist[v] )
                {
                    dist[v] = temp;
                    Decrease( position[v] );
                }
            }
        }
    }
    return;
}

void Output( void )
{
    printf( "%d\n", dist[N] );
    return;
}

void DeleteMin( void )
{
    int n = heap[size], d = dist[n];
    int i = 1, child = dist[heap[2]] < dist[heap[3]] ? 2 : 3;    
    heap[size--] = 0;
    while ( dist[heap[child]] < d )
    {
        position[heap[i] = heap[child]] = i;                        
        i = child;
        child <<= 1;
        if ( dist[heap[child+1]] < dist[heap[child]] )
        {
            ++child;
        }        
    }
    position[heap[i] = n] = i;
    return;
}

void Decrease( int i )
{
    int n = heap[i], d = dist[n];
    unsigned parent = (unsigned)i >> 1;
    while ( dist[heap[parent]] > d )
    {
        position[heap[i] = heap[parent]] = i;
        i = parent;
        parent >>= 1;
    }
    position[heap[i] = n] = i;
    return;
}

另，我在研究配对堆和斐波那契堆，近日可能贴出代码。

顶~

近几日研究了配对堆( Pairing Heap )

先贴出配对堆解POJ3159的代码，依然是标C实现

#include <stdio.h>

#define INF  (0x7F7F7F7F)
#define MAXE (150005)
#define MAXV (30005)

struct edge
{
    int vertex, weight;
    struct edge *next;
} pool[MAXE], *e = pool, *adj[MAXV];

int fchild[MAXV], prev[MAXV], next[MAXV], top;
int dist[MAXV], N, M;
char marked[MAXV];

void Input( void );
void Init( void );
void Solve( void );
void Output( void );

void Pop( void );
void Decrease( int i );
int Merge( int A, int B );

int main( void )
{
    Input();
    Init();
    Solve();
    Output();    
    return 0;
}

void Input( void )
{
    int i, j, k, temp;
    scanf( "%d %d", &N, &M );
    getchar();
    while ( M-- )
    {
        i = 0;
        while ( ' ' != ( temp = getchar() ) )
        {
            i *= 10;
            i += ( temp & 0xf );
        }
        j = 0;
        while ( ' ' != ( temp = getchar() ) )
        {
            j *= 10;
            j += ( temp & 0xf );
        }
        k = 0;
        while ( '\n' != ( temp = getchar() ) )
        {
            k *= 10;
            k += ( temp & 0xf );
        }        
        e->vertex = j;
        e->weight = k;
        e->next = adj[i];
        adj[i] = e++;
    }
    return;
}

void Init( void )
{
    int i, j;
    dist[top = 1] = 0;
    dist[2] = INF;
    fchild[1] = 2;
    prev[2] = 1;    
    for ( i = 2, j = 3; j <= N; ++i, ++j )
    {
        dist[j] = INF;
        next[i] = j;
        prev[j] = i;
    }
    next[N] = 0;
    return;
}

void Solve( void )
{
    int d, v, temp;
    while ( top != N )
    {
        marked[top] = 1;
        e = adj[top];
        d = dist[top];
        Pop();    
        for ( NULL; e; e = e->next )
        {            
            if ( !marked[e->vertex] )
            {
                v = e->vertex;
                temp = d + e->weight;
                if ( temp < dist[v] )
                {
                    dist[v] = temp;
                    Decrease( v );
                }
            }
        }
    }
    return;
}

void Output( void )
{
    printf( "%d\n", dist[N] );
    return;
}

void Pop( void )
{
    static int space[MAXV], * const front = space+1;
    int *rear = front, i, j, k;
    k = next[j = next[i = fchild[top]]];
    while ( i && j )
    {
        *rear++ = Merge( i, j );
        k = next[j = next[i = k]];
    }
    if ( 0 == i )
    {
        i = *--rear;
    }
    while ( front != rear )
    {
        i = Merge( i, *--rear );
    }
    top = i;
    return;
}

void Decrease( int A )
{
    int i;
    if ( A != top )
    {
        i = prev[A];
        if ( A == fchild[i] )
        {
            prev[fchild[i] = next[A]] = i;
        }
        else
        {
            next[i] = next[A];
            prev[next[A]] = i;
        }
        top = Merge( A, top );
    }
    return;
}

int Merge( int A, int B )
{    
    if ( dist[A] < dist[B] )
    {
        prev[B] = A;
        prev[next[B] = fchild[A]] = B;
        fchild[A] = B;
        prev[A] = next[A] = 0;
        return A;
    }
    else
    {
        prev[A] = B;
        prev[next[A] = fchild[B]] = A;
        fchild[B] = A;
        prev[B] = next[B] = 0;
        return B;
    }
}

附上自己捣鼓的配对堆的简单模板

#define MAX  (500)

int elem[MAX];
int fchild[MAX], prev[MAX], next[MAX], top, size;

void Init( void );
void Push( int new_elem );
void Pop( void );
void Decrease( int A );
int Merge( int A, int B );

void Init( void )
{
    top = size = 0;
    elem[0] = 0x7f7f7f7f;
    return;
}

void Push( int new_elem )
{
    ++size;
    elem[size] = new_elem;
    fchild[size] = 0;
    top = Merge( top, size );
    return;
}

void Pop( void )
{
    static int space[MAX], * const front = space+1;
    int *rear = front, i, j, k;
    k = next[j = next[i = fchild[top]]];
    while ( i && j )
    {
        *rear++ = Merge( i, j );
        k = next[j = next[i = k]];
    }
    if ( 0 == i )
    {
        i = *--rear;
    }
    while ( front != rear )
    {
        i = Merge( i, *--rear );
    }
    top = i;
    return;
}

void Decrease( int A )
{
    int i;
    if ( A != top )
    {
        i = prev[A];
        if ( A == fchild[i] )
        {
            prev[fchild[i] = next[A]] = i;
        }
        else
        {
            next[i] = next[A];
            prev[next[A]] = i;
        }
        top = Merge( A, top );
    }
    return;
}

int Merge( int A, int B )
{    
    if ( elem[A] < elem[B] )
    {
        prev[B] = A;
        prev[next[B] = fchild[A]] = B;
        fchild[A] = B;
        prev[A] = next[A] = 0;
        return A;
    }
    else
    {
        prev[A] = B;
        prev[next[A] = fchild[B]] = A;
        fchild[B] = A;
        prev[B] = next[B] = 0;
        return B;
    }
}

1.Init函数中将0号元素的值设置为正无穷是为了方便白手起家用Push建堆。
2.每个节点将子结点组织成一个双链表，头结点的prev指向双亲节点，这些都是为了方便删除。
3.Pop(即DeleteMin)的策略我采用了Weiss书中所述的两趟合并法，貌似均摊后是logN的复杂度，详见Weiss书中最后一节。也可利用一个队列实现合并，稍复杂。
4.至少我用在3159这个问题上，我写的配对堆没有显示出比二叉堆更好。
二叉堆AC 94ms
配对堆AC 110ms
5.我这个配对堆的实现是十分粗糙的，没有封装起来，哪个大牛把这个堆写成类了别忘了给小的瞻仰下...非常感谢...

也许是为了动态地增加路径而考虑的~

占位

ls写得太复杂了..
//无向图最小生成树,prim算法,邻接阵形式,复杂度O(n^2)

//返回最小生成树的长度,传入图的大小n和邻接阵mat,不相邻点边权inf

//可更改边权的类型,pre[]返回树的构造,用父结点表示,根节点(第一个)pre值为-1

//必须保证图的连通的!

#define MAXN 200

#define inf 1000000000

typedef double elem_t;

 

elem_t prim(int n,elem_t mat[][MAXN],int* pre){

       elem_t min[MAXN],ret=0;

       int v[MAXN],i,j,k;

       for (i=0;i<n;i++)

              min[i]=inf,v[i]=0,pre[i]=-1;

       for (min[j=0]=0;j<n;j++){

              for (k=-1,i=0;i<n;i++)

                     if (!v[i]&&(k==-1||min[i]<min[k]))

                            k=i;

              for (v[k]=1,ret+=min[k],i=0;i<n;i++)

                     if (!v[i]&&mat[k][i]<min[i])

                            min[i]=mat[pre[i]=k][i];

       }

       return ret;

}

占位

占位

受教了 正在学这个 谢谢了哦~~

我是来占位的~~~