08-图7 公路村村通 （30 分

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

输入格式:

输入数据包括城镇数目正整数N（≤）和候选道路数目M（≤）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。

输出格式:

输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−，表示需要建设更多公路。

输入样例:

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 #include<cstdio> #include<cstring> const int maxn = 1100; const int INF = 1000000000; int map[maxn][maxn],c[maxn]; bool vis[maxn] = {false}; int n,m;void prime(){memset(c,0,sizeof(c));vis[1] = true;for(int i = 1; i <= n; i++){c[i] = map[i][1];}int sum = 0,flag = 0;for(int i = 2; i <= n; i++){int u = -1,MIN = INF;for(int j = 1; j <= n; j++){if(vis[j] == false && c[j] < MIN){u = j;MIN = c[j];}}if(u == -1){flag = 1;break;}vis[u] = true;sum += MIN;for(int v = 1; v <= n; v++){if(vis[v] == false && c[v] > map[u][v]){c[v] = map[u][v];}}}if(flag == 1){printf("-1");}else{printf("%d",sum);} }int main(){scanf("%d%d",&n,&m);int u,v;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;}}}for(int i = 1; i <= m; i++){scanf("%d%d",&u,&v);scanf("%d",&map[u][v]);map[v][u] = map[u][v];}prime();return 0; }

 

转载于:https://www.cnblogs.com/wanghao-boke/p/9982657.html

创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的08-图7 公路村村通 （30 分的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。