Reiks的技术博客

C/C++/STL/Algorithm/D3D
posts - 17, comments - 2, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

日历

<2009年8月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

搜索

  •  

最新评论

MST-Kruskal

Posted on 2009-08-28 09:17 reiks 阅读(274) 评论(0)  编辑 收藏 引用 所属分类: 算法与数据结构
#include <iostream>
#include 
<fstream>
#include 
<algorithm>
using namespace std;

struct Edge
{
    
int x, y, w; /*边集,边(x,y),权为c*/
}
e[20001];

int rank[1001]; /*节点的秩*/
int p[1001]; /*p[x]表示x节点父节点*/
int ans=0;
int ma;


void Make(int x)
{
    p[x] 
= x;
    rank[x] 
= 1;
}


int Find(int x) /*查找x所在集合子树的根*/
{
    
if (x == p[x]) return x;
    
return p[x] = Find( p[x] );;
}


void Union(int x, int y, int c)
{
    x 
= Find(x);
    y 
= Find(y);
    
if ( x != y ) /*若x,y不属于同一集合*/
    
{
        
if ( rank[x] > rank[y] ) /*将秩较小的树连接到秩较大的树后*/
        
{
            p[y] 
= x;
        }
 
        
else
        
{
            
if(rank[x] == rank[y])
                rank[y]
++;
            p[x] 
= y;
        }

        ans 
+= c;
        ma
++;
    }

}


bool cmp (const Edge & a, const Edge & b)
{
    
return a.w > b.w;
}


int N, M;

int main()
{
    
int n; /*边的条数*/
    
int i;
    
//ifstream in("123.txt");
    ans=0;
    ma 
= 1;
    scanf(
"%d %d"&N, &M);
    
//cin >> N >> M;
    for ( i = 1; i <= N; ++i)
        Make(i);
    
for ( i = 0; i < M; ++i)
    
{
        scanf(
"%d %d %d"&e[i].x, &e[i].y, &e[i].w);
    }

    
    sort(e, e 
+ M, cmp); /*按权值非降序排序*/

    
for ( i = 0; i < M; ++i)
    
{
        Union(e[i].x, e[i].y, e[i].w);
    }

    
if (ma == N)
        printf(
"%d", ans);
    
else
        printf(
"-1");
    
//system("pause");
    return 0;
}


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