prime算法邻接表写法

#include <iostream>

#include <queue>

using namespace std;

typedef struct 

{

    long v;

    long next;

    long cost;

}Edge;

typedef struct 

{

    long v;

    long cost;

}node;

bool operator <(const node &a,const node &b)

{

    return a.cost>b.cost;

}

priority_queue<node> q;

const long MAXN=10000;

Edge e[MAXN];

long p[MAXN];

bool vist[MAXN];

long m,n;

long from,to,cost;

void init()

{

    memset(p,-1,sizeof(p));

    memset(vist,0,sizeof(vist));

    while (!q.empty())

    {

        q.pop();

    }

    long i;

    long eid=0;

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

    {

        scanf("%ld %ld %ld",&from,&to,&cost);

        e[eid].next=p[from];

        e[eid].v=to;

        e[eid].cost=cost;

        p[from]=eid++;

        //以下适用于无向图

        swap(from,to);

        e[eid].next=p[from];

        e[eid].v=to;

        e[eid].cost=cost;

        p[from]=eid++;

    }

}

void print(long cost)

{

    printf("%ld\n",cost);

}

void Prime()

{

    long cost=0;

    init();

    node t;

    t.v=from;//选择起点

    t.cost=0;

    q.push(t);

    long tt=0; 

    while (!q.empty()&&tt<m)

    {

        t=q.top();

        q.pop();

        if (vist[t.v])

        {

            continue;

        }

        cost+=t.cost;

        ++tt;

        vist[t.v]=true;

        long j;

        for (j=p[t.v];j!=-1;j=e[j].next)

        {

            if (!vist[e[j].v])

            {

                node temp;

                temp.v=e[j].v;

                temp.cost=e[j].cost;

                q.push(temp);

            }

        }

    }

    print(cost);

}

int main()

{

    while (scanf("%ld %ld",&m,&n)!=EOF)

    {

        Prime();

    }

    return 0;

}
巴特西

prime算法邻接表写法

最新文章

热门文章
