最小生成树

时间：2010-04-12 来源：buptstehc

来源:Dark roads

利用Prim算法求最小生成树，由于C+的STL中的priority_queue不提供修改队列中元素值的操作，故自己用二叉堆写了个最小优先队列。而在写adjust_heap()时犯了个小错，仅将父结点与子结点做了一次比较，后经超哥提醒，改为先判断最小结点的编号，再交换值。

#include <stdio.h>
#include <list>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

const int junc_size = 200002;

typedef struct
{
    int id, cost;
}junc;

vector< list<junc> > map(junc_size); /*adj list.*/
junc heap[junc_size]; /*minimun priority queue.*/
int pos[junc_size]; /*location of every node in queue.*/
bool inqueue[junc_size];
int m, n, x, y, z;

void swap(int *a, int *b)
{
    int temp;

    temp = *a;
    *a = *b;
    *b = temp;
}

void adjust_heap(int num)
{
    int p, lchild, rchild, minor;

    p = num;
    while(true)
    {
        lchild = p * 2;
        rchild = p * 2 + 1;

        /*choose the minimum node id.*/
        if((lchild <= m) && heap[p].cost > heap[lchild].cost)
            minor = lchild;
        else
            minor = p;

        if((rchild <= m) && heap[minor].cost > heap[rchild].cost)
            minor = rchild;

        if(minor != p)
        {
            swap(&(pos[heap[minor].id]), &(pos[heap[p].id]));
            swap(&(heap[minor].cost), &(heap[p].cost));
            swap(&(heap[minor].id), &(heap[p].id));

            p = minor;
        }
        else
            break;
    }
}

/*adjust heap after the node's key has been decreased.*/
void decrease_key(int num)
{
    int p = num / 2, child = num;

    while(p)
    {
        if(heap[child].cost < heap[p].cost)
        {
            swap(&(pos[heap[child].id]), &(pos[heap[p].id]));
            swap(&(heap[child].cost), &(heap[p].cost));
            swap(&(heap[child].id), &(heap[p].id));
            child = p;
            p = child / 2;

            continue;
        }

        break;
    }
}

void build_heap()
{
    int i, j;

    for(i = m / 2; i > 0; i--)
        adjust_heap(i);
}

void pop(void)
{
    pos[heap[m].id] = 1;
    heap[1].cost = heap[m].cost;
    heap[1].id = heap[m].id;

    m--;
    adjust_heap(1);
}

int top(void)
{
    return heap[1].cost;
}

bool empty(void)
{
    return m == 0;
}

int main(void)
{
    int i, u, sum, pay, size;
    junc jc;

    while(scanf("%d%d", &m, &n) && (m || n))
    {
        sum = 0;
        for(i = 0; i < n; i++)
        {
            scanf("%d%d%d", &x, &y, &z);

            jc.id = y + 1;
            jc.cost = z;
            map[x + 1].push_back(jc);

            jc.id = x + 1;
            jc.cost = z;
            map[y + 1].push_back(jc);

            sum += z;
        }

        for(i = 1; i <= m; i++)
        {
            heap[i].cost = INT_MAX;
            heap[i].id = pos[i] = i;
            inqueue[i] = true;
        }
        heap[1].cost = 0;

        size = m;
        build_heap();

        pay = 0;
        while(!empty())
        {
            pay += top();
            u = heap[1].id;
            inqueue[u] = false;

            pop();
            for(list<junc>::iterator iter = map[u].begin(); iter != map[u].end(); iter++)
            {
                if(inqueue[(*iter).id] && ((*iter).cost < heap[pos[(*iter).id]].cost))
                {
                    heap[pos[(*iter).id]].cost = (*iter).cost;
                    decrease_key(pos[(*iter).id]);
                }
            }

        }

        printf("%d\n", sum - pay);

        for(i = 1; i <= size; i++)
            map[i].clear();
    }

    return 0;
}