POJ 1861 Network [最小生成树算法MST-kruskal 数据结构-并查集 union-find sets]

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 03 月 28 日

跟这个prim算法最小生成树http://blog.csdn.net/hzyhouzhiyuan/archive/2011/01/23/6159382.aspx

两个算法,邻接矩阵存图时,prim适用于稠密图,kruskal适于用稀疏图。

代码还是比较清晰明了的,输入所有边,进行排序,贪心+并查集求出MST。

#include <cstdio>  
#include <cstring>  
#include<algorithm>  
using namespace std;  
const int MAXSIZE = 1050;    
int rank[MAXSIZE];    // 节点高度的上界    
int parent[MAXSIZE]; // 根节点    
int FindSet(int x){// 查找+递归的路径压缩    
    if( x != parent[x] ) parent[x] = FindSet(parent[x]);    
    return parent[x];    
}    
void Union(int root1, int root2){    
    int x = FindSet(root1), y = FindSet(root2);    
    if( x == y ) return ;    
    if( rank[x] > rank[y] ) parent[y] = x;    
    else{    
        parent[x] = y;    
        if( rank[x] == rank[y] ) ++rank[y];    
    }    
}    
void Initi(int n){    
    memset(rank, 0, sizeof(rank));    
    for( int i=0; i <=n; ++i ) parent[i] = i;    
}    
struct hubconnect{  
    int a,b;  
    int len;  
    bool flag;  
}hubconnects[15005];  
bool cmp(hubconnect h1,hubconnect h2)  
{return h1.len<h2.len;}  
int main()  
{  
    freopen("1.txt","r",stdin);  
    int n,m;  
    hubconnect temp;  
    scanf("%d%d",&n,&m);  
    Initi(n);  
    memset(hubconnects,0,sizeof(hubconnects));  
    for (int i=0;i<m;i++)  
    {  
        scanf("%d%d%d",&hubconnects[i].a,&hubconnects[i].b,&hubconnects[i].len);  
    }  
    sort(hubconnects,hubconnects+m,cmp);  
    int maxlen=0,mycount=0;  
    for (int i=0;i<m;i++)  
    {  
        if( FindSet(hubconnects[i].a) !=FindSet(hubconnects[i].b))  
        {  
            Union(hubconnects[i].a,hubconnects[i].b);  
            hubconnects[i].flag=1;  
            mycount++;  
            if(maxlen<hubconnects[i].len) maxlen=hubconnects[i].len;  
            if(mycount >= n-1) break;  
        }  
    }  
    printf("%d\n%d\n",maxlen,mycount);  
    int i=0;  
    while(mycount)  
    {  
        if(hubconnects[i].flag)  
        {  
            printf("%d %d\n",hubconnects[i].a,hubconnects[i].b);  
            mycount--;  
        }  
        i++;  
    }  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期二, 2017 年 10 月 24 日