HDU－1233 还是畅通工程(最小生成树&并查集)

//prim（加点法）
#include <iostream>
#include <algorithm>
#include <string.h>
#include <cstdio>
#include <string>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
//#include <unordered_map>
#define Fbo friend bool operator < (node a, node b)
#define mem(a, b) memset(a, b, sizeof(a))
#define FOR(a, b, c) for (int a = b; a <= c; a++)
#define RFOR(a, b, c) for (int a = b; a >= c; a--)
#define off ios::sync_with_stdio(0)
#define sc(a) scanf("%d",&a) 
bool check1(int a) { return (a & (a - 1)) == 0 ? true : false; }

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int Maxn = 1005;
const double pi = acos(-1.0);
const double eps = 1e-8;

/*
minl存储找到最小的边
minid存储最小边的节点号
sum存储最小生成树的和
*/
int vis[1010];//用来标记0和1  表示这个点是否被选择过
int map1[1010][1010];//邻接矩阵用来存储图的信息
int dis[1010];//记录任意一点到这个点的最近距离
int n, m, minl, minid, sum;
int prim()
{
    mem(vis, 0);
    sum = 0;
    /*①选定1为起始点，初始化,比如从1开始，那么先把所有边的值更新到dis */
    for (int i = 1; i <= n; i++){
        dis[i] = map1[1][i];
    }
    //dis[1] = 0;
    //vis[1] = 1;//选择起点
    /*循环找最小边，循环n-1次*/
    for (int i = 2; i <= n; i++)//②初始化min,minid，防止后面的用上一次数据
    {
        minl = INF;
        minid = 0;
    //③找出当前数组最小的边，且这个节点未加入最小生成树
        for (int j = 2; j <= n; j++)
        {
            if (vis[j] == 0 && dis[j] < minl)//循环找出dis的最小边的节点
            {
                minl = dis[j];
                minid = j;
            }
        }
    //④sum+=min,和把dis置为0，表示这个节点已经找到最小边
        sum += minl;
        vis[minid] = 1;//表示找到了 
    //⑤找到最小的节点之后更新数组dis
        for (int j = 2; j <= n; j++)//添入新点后更新最小距离
        {
            if (vis[j] == 0 && dis[j] > map1[minid][j])//当加入边之后，更新dis
                dis[j] = map1[minid][j];
        }
    }
    return sum;
}
int main()
{
    while (scanf("%d", &n), n)//n是点数
    {
        int m = n * (n - 1) / 2;//m是边数
        memset(map1, INF, sizeof(map1));//map1是邻接矩阵存储图的信息,初始化图
        for (int i = 0; i < m; i++)//构造图
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            //if (c < map1[a][b])//防止重边
                map1[a][b] = map1[b][a] = c;
        }
        printf("%d\n",prim());
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <string.h>
#include <cstdio>
#include <string>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
//#include <unordered_map>
#define Fbo friend bool operator < (node a, node b)
#define mem(a, b) memset(a, b, sizeof(a))
#define FOR(a, b, c) for (int a = b; a <= c; a++)
#define RFOR(a, b, c) for (int a = b; a >= c; a--)
#define off ios::sync_with_stdio(0)
#define sc(a) scanf("%d",&a) 
bool check1(int a) { return (a & (a - 1)) == 0 ? true : false; }

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int Maxn = 1005;
const double pi = acos(-1.0);
const double eps = 1e-8;

int a[Maxn]; //并查集
int n, m;//点，边

struct Edge {
    int u, v, w;
}edge[Maxn*Maxn];//定义边

bool cmp(Edge a, Edge b) {
    return a.w < b.w;
}

int find(int u) {
    return a[u] == u ? u : find(a[u]); //查询并查集，返回u的根节点
}

int kruskal() {
    int ans = 0;
    FOR(i, 1, n) //初始化，开始每个村庄都是单独的集
        a[i] = i;
    sort(edge + 1, edge + 1 + m, cmp);//排序后能把最短的边一次插入到图中
    FOR(i, 1, m) {
        int b = find(edge[i].u);//边的前端点，u属于哪个集
        int c = find(edge[i].v);//边的后端点，v属于哪个集
        if (b == c)continue;//产生了圈，丢弃这个边
        a[c]=b;//合并
        ans += edge[i].w;//计算MST
    }
    return ans;
}

int main() {
    while (~scanf("%d", &n), n) {
        m = n * (n - 1) / 2;
        FOR(i, 1, m) {
            scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w); //两个村庄编号及距离(权值)
        }
        printf("%d\n", kruskal());
    }
    return 0;
}