精品一区二区久久久久久久网站,亚洲AV乱码久久精品蜜桃,久久精品国产69国产精品亚洲

(轉)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);

}

if (tt == m)

print(cost);

else

printf ("?\n");//按題目要求輸出不能構成最小生成樹時的解;

}

int main()

{

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

{

Prime();

}

return 0;

}

posted on 2010-01-11 20:25 此最相思閱讀(152) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

misschuer

導航

公告

留言簿

隨筆分類

文章分類

隨筆檔案

文章檔案

閱讀排行榜

評論排行榜

常用鏈接

統計

積分與排名

百事通

最新評論

(轉)Prime+鄰接表