数据结构电网建设造价计算一

1、假设一个城市有n稍僚敉视个小区，要实现n个小区之间的电网都能够相互接通，构造这个城市n个小区之间的电网，使总工程造价最低。请设计一个能满足要求的造价方案。

2、n个小区之间最多可以有n(n-1)/2条线路，选择其中的n-1条使总的耗费最少。

3、可以用连通网来表示n个城市之间以及n个城市之间可能设置的电网线路，其中网的顶点表示小区，边表示两个小区之间的线路，赋予边的权值表示相应的代价

4、对于n个顶点的连通网可以建立许多不同的生成树，每一颗生成树都可以是一个电路网。

5、我们要选择总耗费最少的生成树，就是构造连通网的最小代价生成树的问题，一颗生成树的代价就是树上各边的代价之和。

6、设G=(V, E)是具有n个顶点的网络，T=(U, TE)为G的最小生成树，U是T的顶点集合，TE是T的边集合。