misschuer

常用链接

统计

积分与排名

百事通

最新评论

(转)Kruskal+邻接表

#include <iostream>
#include <queue>
using namespace std;

const long MAXN=10000;

long hash[MAXN];

long m,n;//点数 边数
//m标号从1开始
typedef struct
{
    long from;
    long to;
    long cost;
}Edge;

bool operator <(const Edge &a, const Edge &b)
{
    return a.cost>b.cost;
}

priority_queue<Edge> q;
Edge e;

void MakeSet()
{
    long i;
    for (i=0;i<=m;++i)
    {
        hash[i]=i;
    }
}

long Find(long i)
{
    long r=i;
    while (hash[r]!=r)
    {
        r=hash[r];
    }
    
    while (hash[i]!=r)
    {
        long j=hash[i];
        hash[i]=r;
        i=j;
    }
    
    return r;
}

void Unition(long x,long y)
{
    long fx=Find(x);
    long fy=Find(y);
    
    if (fx!=fy)
    {
        hash[fx]=fy;
    }
}

void Init()
{
    
    while (!q.empty())
    {
        q.pop();
    }
    MakeSet();
    long i;
    for(i=0;i<n;++i)
    {
        scanf("%ld %ld %ld",&(e.from),&(e.to),&(e.cost));//得到源点 终点
        q.push(e);
        //以下为无向图的处理
        swap(e.from,e.to);
        q.push(e);
    }
}

void print(long cost)
{
    printf("%ld\n",cost);
}

void Kruskal()
{
    Init();
    
    long t=0;//表示合并次数
    
    long cost=0;
    
    Edge e;
    while (!q.empty()&&t<m-1)
    {
        e=q.top();
        long v1=e.from;
        long v2=e.to;
        if (Find(v1)!=Find(v2))
        {
            Unition(v1,v2);
            cost+=e.cost;
            ++t;
        }
        q.pop();
    }
    if (t == m - 1)
        print(cost);
    else
        printf ("?\n");
}

int main()
{
    while(scanf("%ld %ld",&m,&n)!=EOF)//输入点与边
    {
        Kruskal();
    }
    return 0;
}

posted on 2010-01-11 20:26 此最相思 阅读(270) 评论(0)  编辑 收藏 引用


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