这是一道典型的最小生成树的题目, 利用Kruskal算法,先按照road的长度排序,若当前的road未在连接好的“城市组”里,则连通它。直到所有的城市全部连通,即所铺路径最短。
// runtime: 6ms // space: 488K #include <iostream> #include <algorithm> using namespace std; struct Road { int from; int to; int distance; bool operator< (const Road& r) const { return distance < r.distance; } }; const int MAX = 100; Road road[MAX * MAX]; int father[MAX]; int height[MAX]; // 并查集代码 void Initial(int n) { for (int i = 0; i <= n; ++i) { father[i] = i; height[i] = 0; } } int Find(int x) { if (x != father[x]) { father[x] = Find(father[x]); } return father[x]; } void Union(int x, int y) { x = Find(x); y = Find(y); if (x != y) { if (height[x] > height[y]) { father[y] = x; } else if (height[x] < height[y]) { father[x] = y; } else { father[x] = y; height[y]++; } } } int Kruskal(int cityNum, int roadNum) { Initial(cityNum); sort(road, road + roadNum); int sum = 0; for (int i = 0; i < roadNum; ++i) { Road current = road[i]; if (Find(current.from) != Find(current.to)) { // 核心代码 Union(current.from, current.to); sum += current.distance; } } return sum; } int main() { int cityNum; while (cin >> cityNum) { if (cityNum == 0) break; int roadNum = cityNum * (cityNum - 1) / 2; for (int i = 0; i < roadNum; ++i) { cin >> road[i].from >> road[i].to >> road[i].distance; } cout << Kruskal(cityNum, roadNum) << endl; } return 0; }