题目描述:
校园网是为学校师生提供资源共享、信息交流和协同工作的计算机网络。校园网是一个宽带、具有交互功能和专业性很强的局域网络。如果一所学校包括多个学院及部门，也可以形成多个局域网络，并通过有线或无线方式连接起来。原来的网络系统只局限于以学院、图书馆为单位的局域网，不能形成集中管理以及各种资源的共享，个别学院还远离大学本部，这些情况严重地阻碍了整个学校的网络化需求。
无向连通图G=（V，E）来表示通信网络，V表示顶点集，E表示边集。把各个单位抽象为图中的顶点，顶点与顶点之间的边表示单位之间的通信网络，边的权值表示布线的费用。如果两个节点之间没有连线，代表这两个单位之间不能布线，费用为无穷大。现在需要设计网络电缆布线，将各个单位的局域网络连通起来，如何设计能够使费用最少呢？
输入描述:
第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据的第一行是两个整数n,c(1<n,c<1000)表示该测试数据有n个顶点c条边。
随后的c行，每行有3个正整数u,v,w(0<u,v<=n, 0<w<10000),分别表示边的两个顶点编号u,v及两顶点之间的费用。
输出描述:
对于每一组输入，输出最小费用值。
每组的输出占一行。
样例输入:
复制
2
7 12
1 2 23
1 6 28
1 7 36
2 3 20
2 7 1
3 4 15
3 7 4
4 5 3
4 7 9
5 6 17
5 7 16
6 7 25
4 6
1 2 10
1 4 5
1 3 8
2 3 8
2 4 11
3 4 8
样例输出:
57
21------------------------------------------------------------------------------------------------------------Prim模板题，注意最后输出时注意也有可能建立不了最小生成树的情况，也就是权重之和可能为无穷大。C++代码：
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn =
1002;
int mp[maxn][maxn],lowcost[maxn];
bool flag[maxn];
const int INF =
0x3f3f3f3f;
void Prim(
int n,
int u0,
int mp[maxn][maxn]){
flag[u0] =
true;
int i,j;
for(i =
1;i <= n; i++
){
if(i !=
u0){
lowcost[i] =
mp[u0][i];
flag[i] =
false;
}
else{
lowcost[i] =
0;
}
}
for(i =
1; i <= n; i++
){
int temp = INF,t =
u0;
for(j =
1; j <= n; j++
){
if(!flag[j] && lowcost[j] <
temp){
t =
j;
temp =
lowcost[j];
}
}
if(t == u0)
break;
flag[t] =
true;
for(j =
1; j <= n; j++
){
if(!flag[j] && lowcost[j] >
mp[t][j]){
lowcost[j] =
mp[t][j];
}
}
}
}
int main(){
int m;
cin>>
m;
while(m--
){
int n,c;
cin>>n>>
c;
for(
int i =
1; i <= n; i++
){
for(
int j =
1; j <= n; j++
)
if(i!=
j)
mp[i][j] =
INF;
else
mp[i][j] =
0;
}
int u,v,w;
for(
int i =
1; i <= c; i++
){
cin>>u>>v>>
w;
if(w <
mp[u][v])
mp[u][v] = mp[v][u] =
w;
}
Prim(n,1,mp);
int sum =
0;
for(
int i =
1; i <= n; i++
)
sum+=
lowcost[i];
if(sum < INF) //注意！！！！！！！！！！！
cout<<sum<<endl;
else
cout<<0<<endl;
}
return 0;
}
转载于:https://www.cnblogs.com/Weixu-Liu/p/10644215.html
