flash网站的优势,按月付费网站建设,做网站的参考书,做展示型网站便宜吗现有村落间道路的统计数据表中#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 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
