Hdu1233 最小生成树的一些笔记

1/一棵树的任意两个节点都有路径

2/任何两个顶点之间都有边（弧）相连称为完全图
完全图有n个节点时，总共有n*(n-1)/2条边

3/生成树只能有n-1条边

prim的实现：

起始点start

u=start;
do{
　　将u的所有相连的边储存到一个最小堆中

　　while（堆非空）
　　　　利用最小堆性质弹出最小权值的边(这些边的起始点u一定visited)
　　　　此边的顶点分别是u和v
　　　　判断点v是否visited
　　　　若是则重新在堆中查找
　　　　若否则将该边保存至MST中，break结束；
}while（MST中边数达到N-1）

prim的实现2：//严蔚敏数据结构：

MST中的点集为U
主要思想是每次都从V-U到U的边中找到权值最小的边
找到该边时将该边在V-U中的顶点转移到U中

具体实现是：
利用一个closedge[]数组，closedge[i].lowcost表示V-U中的点i到U的最小权值
如果只是求最小生成树的权值和的话，直接创建lowcost[]数组更好

lowcost[]数组实际上运用了一个窍门
若点v到u0的lowcost[v]=1
当u1加入U之后
若v到u1有边，且权值比lowcost[v]小
则lowcost[v]=w(u1,v)
总之，lowcost[]总能找到U到V-U中最小权值的边

将V-U中的点移至U中的方法是利用visited[]数组标记，visited[U]=1,visited[V-U]=0
U==V时，辅助变量cnt==n

while(U!=V){
　　for U中的点u
　　　　for V-U中的点v
　　　　　　若(u,v)的权值w(u,v)小于closedge[v].lowcost)
　　　　　　closedge[v].lowcost=w(u,v)
　　　　　　若w(u,v)<min
　　　　　　　　min=w(u,v)

}

kruskal的实现：

将所有边都放进最小堆中

while(MST中边数为N-1)
　　从最小堆中弹出最小权值边
　　该边的两个顶点u,v，可利用并查集找出u与v的根
　　若u的根与v的根相同，则说明u与v在同一连通分量中，此时，添加此边会在MST中形成环，故将该边舍弃
　　若不同，则将此边加入MST中

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1233

贴上Prim代码：

#include<iostream>
#include<cstring>
#include<cmath>
#define INF 9999999
using namespace std;

int graph[100][100];
int lowcost[100];
int n;
bool vis[100];
int Min,sum,cur;

int prim(){
    cur=1;
    sum=0;
    vis[1]=1;

    for(int cnt=1;cnt<n;cnt++){                     //n-1´Î

        for(int i=1;i<=n;i++)
            if(!vis[i] && graph[cur][i]<lowcost[i])
                lowcost[i]=graph[cur][i];

        Min=INF;                                    
        for(int i=1;i<=n;i++)
        {
            if(!vis[i] && lowcost[i]<Min){
                Min=lowcost[i];
                cur=i;
            }
        }
        vis[cur]=1;
        sum+=Min;
    }    
    return sum;
}

int main (){

    while(cin>>n){ 
        if(!n)
            break;

        int u,v,w;
        memset(graph,INF,sizeof(graph));           
        memset(vis,0,sizeof(vis));
        memset(lowcost,INF,sizeof(lowcost));
        for(int i=0;i<n*(n-1)/2;i++){
            cin>>u>>v>>w;
            graph[u][v]=w;
            graph[v][u]=w;
        }

        cout<prim()<<endl;
    }
    return 0;
}

View Code

贴上Kruskal代码

//并查集的实现
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int maxn=100;
int parent[maxn];
int Rank[maxn];
int n;//集元素的个数 

struct edgenode{
    int u,v,w;
};

int find(int x){
    while(parent[x]!=x)
        x=parent[x];
    return x;
}

void Union(int x,int y){

    //x=find(x);
    //y=find(y);
    if(Rank[x]==Rank[y])    //同秩的时候，令y成为x的父节点 
    {
        Rank[y]++;
        parent[x]=y;
    } 
    else if(Rank[x]>Rank[y])
        parent[y]=x;
    else
        parent[x]=y;

}   //加权规则 

void makeSet(){
    for(int i=1;i<=n;i++)
    {
        Rank[i]=0;
        parent[i]=i;
    }
}

bool cmp (edgenode& ed1,edgenode& ed2)
{
    return ed1.w<ed2.w;
}

edgenode edge[maxn*maxn/2];
int sum;
int x,y,k;

int kruskal(){

    sum=0;
    sort(edge,edge+k,cmp);      
    for(int i=0;i<k;i++){  
        x=find(edge[i].u);
        y=find(edge[i].v);
        if(x!=y){
            parent[x]=y;
            sum+=edge[i].w;      
        }
    }
    return sum;
}

int main (){

    while(cin>>n&&n)
    {    

        k=n*(n-1)/2;    //边数k
        for(int i=0;i<k;i++) 
            cin>>edge[i].u>>edge[i].v>>edge[i].w;

        makeSet();
        cout<<kruskal()<<endl;
    }
    return 0;
}

View Code