misschuer

常用链接

统计

积分与排名

百事通

最新评论

(转)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 此最相思 阅读(145) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理