结构设计网站,宁波专业优化网站制作公司,wordpress打开要卡一下,益阳市城乡和住房建设部网站现有村落间道路的统计数据表中#xff0c;列出了有可能建设成标准公路的若干条道路的成本#xff0c;求使每个村落都有公路连通所需要的最低成本。 输入格式: 输入数据包括城镇数目正整数N#xff08;≤#xff09;和候选道路数目M#xff08;≤#xff09;#xff1b;随… 现有村落间道路的统计数据表中列出了有可能建设成标准公路的若干条道路的成本求使每个村落都有公路连通所需要的最低成本。 输入格式: 输入数据包括城镇数目正整数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 #includecstdio
#includecstring
const int maxn 1010;
const int INF 100000000;int map[maxn][maxn],c[maxn];
bool vis[maxn] {false};
int n,m;void init();
void prim();int main(){scanf(%d%d,n,m);init();int u,v;for(int i 0; i m; i){scanf(%d%d,u,v);scanf(%d,map[u][v]);map[v][u] map[u][v];}prim();return 0;
}void init(){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;}}}
}void prim(){vis[1] true;for(int i 1; i n; i){c[i] map[i][1];}int sum 0;bool flag true;for(int i 2; i n; i){int u -1,min INF;for(int j 1; j n; j){if(!vis[j] c[j] min){u j;min c[j]; }}if(u -1){flag false;break;}vis[u] true;sum min;for(int v 1; v n; v){if(!vis[v] c[v] map[u][v]){c[v] map[u][v];}}}if(flag) printf(%d,sum);else printf(-1);
} prim最小生成树算法---加点法即选取集合中代价最小的点生成树 转载于:https://www.cnblogs.com/wanghao-boke/p/10851398.html
