代码

/*
思路，将边集加入到最小优先队列，每次取出一个最小边，如果边的两个端点有一个没有访问过，说明加入这条边，就没有构成环。可以加入。
突然发现这个思路是错的。判断是不是环，我的说法是错误的。还没有想到解决办法。

如果解决了：加入一条边，能够判断是否形成环。能把这点实现，并优化就可以了。
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100;
int p[maxn][maxn];
int vis[maxn];
int n,m;
struct node
{
    int f,t,w;
    node(int f, int t, int w):f(f),t(t),w(w){}
};
struct com
{
    bool operator()(node a, node b){
        return a.w > b.w;
    }
};
int ans;
int main()
{
    fill(p[0],p[maxn-1]+maxn,INT_MAX);
    fill(vis,vis+maxn,0);
    cin >> n >> m;
    int f,t,w;
    priority_queue<node,vector<node>, com> pq;
    for(int i=0; i<m; i++){
        cin >> f >> t >> w;
        pq.push(node(f,t,w));
    }
    for(int i=1; i<=m; i++){
        node tem = pq.top(); pq.pop();
        if(!vis[tem.f] || !vis[tem.t]){
            vis[tem.f] = 1; vis[tem.t] = 1;
            ans += tem.w;
        }
    }
    cout << ans << endl;
    return 0;
}

/*
今天学习了复习了并查集，发现并查集可以解决环路问题。于是把代码。修改了一下。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000;
int p[maxn];
struct Node
{
    int f,t,w,index;
    Node(){}
    Node(int f,int t,int w,int index):f(f),t(t),w(w),index(index){}
}node[maxn];
struct com
{
    bool operator()(Node a, Node b){
        return a.w > b.w;
    }
};
priority_queue<Node,vector<Node>,com> pq;//小根堆
int n,m;
int ans;

int Find(int x){return p[x]==x ? x : Find(p[x]);}
int main()
{
    cin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        cin >> node[i].f >> node[i].t >> node[i].w;
        node[i].index = i;
        pq.push(node[i]);
    }
    for(int i=1; i<=n; i++){p[i]=i;}
    for(int i=1; i<=m; i++)
    {
        Node tem = pq.top(); pq.pop();
        cout <<tem.index << ' ' << tem.w << endl;
        int edge = tem.index;
        int x = Find(node[edge].f);
        int y = Find(node[edge].t);
        if(x!=y) {
            ans += node[edge].w;
            p[x] = y;
        }
    }

    cout << ans << endl;
    return 0;
}

*/