题解 | #畅通工程#

//这道题算是比较常规的题了，采用kruskal算法并利用并查集思想求最小生成树
#include "stdio.h"
#include "queue"
using namespace std;
struct Edge{
    int villageS;//源端的村庄编号
    int villageT;//目的端的村庄编号
    int weight;
};
int N,M;//N为道路数目，M为村庄数目
priority_queue<Edge> myPQueue;
int Father[101];//并查集得根存储

bool operator < (Edge lhs,Edge rhs){
    return lhs.weight > rhs.weight;
}

void Init(){
    for (int i = 1; i <= M; ++i) {
        Father[i] = i;
    }
    while (!myPQueue.empty())
        myPQueue.pop();
}

int find(int x){
    if (Father[x] != x){
        Father[x] = find(Father[x]);
    }
    return Father[x];
}

int kruskal(){
    int sum = 0;//存储路径总长
    while (!myPQueue.empty()){
        Edge edge = myPQueue.top();
        myPQueue.pop();
        int villageS = edge.villageS,villageT = edge.villageT;
        if (find(villageS) != find(villageT)){
            Father[find(villageT)] = find(villageS);//Union操作
            sum += edge.weight;
        }
    }
    int count = 0;
    for (int i = 1; i <= M; ++i) {
        if (Father[i] == i)
            ++count;
    }
    if (count != 1)//有多个连通分支，无法形成最小生成树
        return -1;
    else
        return sum;
}

int main(){
    while (scanf("%d",&N)!=EOF){
        if (N == 0)
            break;
        scanf("%d",&M);
        Init();//对邻接矩阵和并查集进行初始化
        int villageS,villageT,weight;
        for (int i = 1; i <= N; ++i) {//道路入优先队列
            scanf("%d%d%d",&villageS,&villageT,&weight);
            Edge edge;edge.villageS = villageS;
            edge.villageT = villageT;edge.weight = weight;
            myPQueue.push(edge);
        }
        int sum = kruskal();
        if (sum != -1)
            printf("%d\n",sum);
        else
            printf("?\n");
    }
}