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


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理