PTA 镖局运镖 (30分)(最小生成树)

镖局运镖 (30分)(最小生成树)"/>

PTA 镖局运镖 (30分)(最小生成树)

镖局的运镖，就是运货（类似现在的物流）。镖局每到一个新地方开展业务，都需要对运镖途中的绿林好汉进行打点。好说话的打点费就比较低，不好说话的打点费就比较高。龙门镖局现在有一趟镖请你来规划路线，已知城市的地图，你需要选择一些道路进行疏通，以便镖局可以到达任意一个城市，要求花费的银子越少越好。

输入格式:

第一行有两个数n和m，n表示有n个城市（编号从1到n），m表示有m条道路。接下来m行，每行形如“a b c”用来表示一条道路，意思是城市a到城市b连通且打点需要花费的银子数是c。

输出格式:

若通过打点能抵达所有城市，则输出最少需要花费的银子总数。若不能抵达所有的城市则输出“impossible”。

输入样例:

3 3
1 2 1
1 3 2
2 3 4

输出样例:

3

解题

最小生成树签到题，还要判断是否成一棵树，因此这里用Kruskal算法
代码：

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;struct edge{int v1, v2, w;
};struct cmp{bool operator ()(const edge e1, const edge e2){return e1.w > e2.w;}
};int FindSet(int Set[], int x)
{if(Set[x] < 0)return x;return Set[x] = FindSet(Set, Set[x]);
}void UnionSet(int Set[], int R1, int R2)
{if(Set[R1] > Set[R2])		//R2 > R1Set[R2] += Set[R1], Set[R1] = R2;elseSet[R1] += Set[R2], Set[R2] = R1;
}bool isOneTree(int Set[], int n)		//判断是不是一棵树
{int k = FindSet(Set, 1);for (int i = 2; i <= n; i++)if(k != FindSet(Set, i))return false;return true;
}int main()
{int n, m, a, b, w;cin >> n >> m;int *Set = new int[n + 1];memset(Set, -1, (n + 1) * sizeof(int));priority_queue<edge, vector<edge>, cmp> q;for (int i = 0; i < m; i++){cin >> a >> b >> w;q.push({a, b, w});}int ans = 0;while (!q.empty()){int a = FindSet(Set, q.top().v1);int b = FindSet(Set, q.top().v2);int w = q.top().w;q.pop();if(a == b)			//如果是同一棵树上的顶点continue;UnionSet(Set, a, b);ans += w;}if(isOneTree(Set, n))cout << ans << endl;elsecout << "impossible" << endl;delete[] Set;system("pause");return 0;
}

c++最小优先队列参考：