首页 > 代码库 > PTA 08-图7 公路村村通 (30分)
PTA 08-图7 公路村村通 (30分)
现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本。
输入格式:
输入数据包括城镇数目正整数NN(\le 1000≤1000)和候选道路数目MM(\le 3N≤3N);随后的MM行对应MM条道路,每行给出3个正整数,分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见,城镇从1到NN编号。
输出格式:
输出村村通需要的最低成本。如果输入数据不足以保证畅通,则输出-1?1,表示需要建设更多公路。
输入样例:
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3
输出样例:
12
/* * 这题边数e <= 3*顶点数 不是稀疏图 故以邻接矩阵进行存储 采用prim算法。 * findMin()函数找最小值可以用最小堆进行优化。 */ #include "iostream" using namespace std; #define INF 999999 int map[1005][1005]; int n, m; int lowCost[1005]; long ans = 0; int findMin() { int minCost = INF; int k, j; for (k = 0, j = 1; j <= n; j++) { if (lowCost[j] && lowCost[j] < minCost) { minCost = lowCost[j]; k = j; } } return k; } int prim() { for (int i = 1; i <= n; i++) { lowCost[i] = map[1][i]; } lowCost[1] = 0; /* 从序号为1的顶点出发生成最小生成树 */ for (int i = 1; i < n; i++) { /* 生成树还需要收n-1个节点 */ int k = findMin(); /* 找到到生成树距离最短的节点 */ if (k) { ans += lowCost[k]; lowCost[k] = 0; for (int j = 2; j <= n; j++) { /* 更新当前的最小生成树 */ if (lowCost[j] && map[k][j] < lowCost[j]) { lowCost[j] = map[k][j]; } } } else { return -1; } } return ans; } void init() { cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { if (i == j) { map[i][j] = 0; } else { map[i][j] = INF; } } while (m--) { int c1, c2, c3; cin >> c1 >> c2 >> c3; map[c1][c2] = map[c2][c1] = c3; } } int main() { init(); cout<<prim()<<endl; }
PTA 08-图7 公路村村通 (30分)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。