Chinaunix首页 | 论坛 | 博客
  • 博客访问: 42441
  • 博文数量: 13
  • 博客积分: 1410
  • 博客等级: 上尉
  • 技术积分: 150
  • 用 户 组: 普通用户
  • 注册时间: 2010-01-11 20:07
文章分类

全部博文(13)

文章存档

2010年(13)

我的朋友

分类: C/C++

2010-01-19 13:29:19

#include <stdio.h>
#include <queue>
#define MAX 100
using namespace std;
typedef struct
{
    int v1,v2,len;
}Node;
Node graph[MAX];
int fa[MAX];
bool operator >(Node a,Node b)
{    return a.len>b.len;}
int Getfa(int i)
{
    if(fa[i]==i) return i;
    fa[i]=Getfa(fa[i]);
    return fa[i];
}
int main()
{
    priority_queue<Node,vector<Node>,greater<Node> >Q;
    for(int i=1;i<=n;i++) fa[i]=i;
    while(!Q.empty()) Q.pop();
    int v1,v2,len;
    while(true)
    {
        Node e;
        e.v1=v1,e.v2=v2,e.len=len;
        Q.push (e);
    }
    int sum=0;
    while(Q.size()!=0)
    {
        Node e=Q.top();
        Q.pop();
        if(Getfa(e.v1)!=Getfa(e.v2))
        {
sum+=len;
            fa[Getfa(e.v2)]=Getfa(e.v1 );
        }
    }
}


阅读(821) | 评论(0) | 转发(0) |
0

上一篇:Dijkstra算法

下一篇:匈牙利算法

给主人留下些什么吧!~~