【codevs1078】最小生成树

problem

solution

codes

//MST-Prim-贪心-堆优化
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 110;
//Graph
int e[maxn][maxn],ans;
//Prim
struct node{
    int v, w;
    node(int v=0, int w=0):v(v),w(w){}
    bool operator < (node b)const{return w>b.w;}
};
priority_queue<node>q;//保存所有可以抵达生成树的边
int book[maxn];
//main
int main(){
    ios::sync_with_stdio(false);
    int n;  cin>>n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin>>e[i][j];
    //将1号顶点加入生成树
    book[1] = 1;
    for(int i = 1; i <= n; i++)
        if(e[1][i])q.push(node(i,e[1][i]));
    //将剩余的n-1个点加入生成树
    for(int i = 2; i <= n; i++){
        //找到所有(与生成树相连的)点里面到生成树距离最短的
        node t = q.top();  q.pop();
        while(book[t.v]){//只有不在生成树里的点才可以加到生成树里面，这里避免重复。
            t = q.top();  q.pop();
        }
        //将该点加入生成树
        book[t.v] = 1;  ans += t.w;
        //用该点的出边松弛其他非生成树点到生成树的距离
        for(int j = 1; j <= n; j++)
            if(!book[j] && e[t.v][j])//当前加入生成树的点可以扩充出的边指向的节点
                q.push(node(j,e[t.v][j]));
    }
    cout<<ans<<"\n";
    return 0;
}

//MST-Kruskal-排序贪心+并查集
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
const int maxn = 110;
//Graph
struct Edge{
    int u, v, w;
    Edge(int u=0, int v=0, int w=0):u(u),v(v),w(w){}
    bool operator < (Edge b)const{return w<b.w;}
};
vector<Edge>e;//边数不确定用vector
//UnionFindSet
int fa[maxn];
void init(int n){for(int i=1;i<=n;i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;}
//main
int main(){
    int n;  cin>>n;
    //从邻接矩阵中提取边
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            int x;  cin>>x;
            if(j >= i)continue;
            e.push_back(Edge(i,j,x));
        }
    }
    sort(e.begin(),e.end());
    LL ans = 0;
    init(n);
    for(int i = 0; i < e.size(); i++){
        int u = e[i].u, v = e[i].v;
        if(find(u) != find(v)){
            merge(u,v);
            ans += e[i].w;
        }
    }
    cout<<ans<<"\n";
    return 0;
}