C++实习题 高手来
发布网友
发布时间：2022-04-26 04:33
共5个回答
热心网友
时间：2022-06-20 19:47
你被分配到设计在广域某些点之间的网络连接。你是给该地区的一个点集，以及可能的路线，可能的电缆连接点对。对于每两点之间可能的途径，您将得到的是需要在这条道路连接点电缆长度。请注意有可能存在两种可能由于点多线。据推测，可能是由于线路连接（直接或间接）在该地区的每两点。
你的任务是设计的区域网络，从而有一个连接（直接或间接每两点之间）（即各点是相互关联的，但不一定是直接电缆），而且总长度所使用的电缆是最小的。
输入格式：（b4.in）
输入文件包含的数据集的数目。每个数据集定义一个所需的网络。集合的第一行包含两个整数：首先定义了给定的点的数量P和第二所给予航线之间的点数R。 R线以下两点之间的定义给定的路线，各以三个整数：前两个数字识别点，第三给出了路线的长度。这些数字之间用空格。一个数据集只给一个数P = 0表示的输入端。数据集之间用一个空行。
点的最大数量为50。在某航线的最大长度为100。可能的路线是无限的。这些节点的确定1和P之间的整数（含）。两点之间的路线i和j可以得到尽可能ij或为J岛
输出格式：（b4.out）
对于每个数据集，一个号码印刷在单独行给出了整个设计的网络中使用的电缆总长度。
Sample Input:
1 0
2 3
1 2 37
2 1 17
1 2 68
3 7
1 2 19
2 3 11
3 1 7
1 3 5
2 3
3 1 91
1 2 32
5 7
1 2 5
2 3 7
2 4 8
4 5 11
3 5 10
1 5 6
4 2 12
0
Sample Output:
0
17
16
26
热心网友
时间：2022-06-20 19:47
# include<iostream>
# include<cstdio>
# include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
int a[52][52],len,vis[55],p;
int prim();
int main()
{
int r,i,j,temp;
while(1)
{
scanf("%d",&p);
if(p==0)
break;
scanf("%d",&r);
for(i=1;i<=p;i++)
for(j=1;j<=p;j++)
a[i][j]=inf;
memset(vis,0,sizeof(vis));
len=0;
while(r--)
{
scanf(" %d %d %d",&i,&j,&temp);
if(temp<a[i][j])
a[i][j]=a[j][i]=temp;
}
vis[1]=1;
printf("%d\n",prim());
}
return 0;
}
int prim()
{
int i,j,k,j_m,temp,ans;
for(k=1;k<p;k++)
{
temp=inf, ans=0;
for(i=1;i<=p;i++)
{
if(!vis[i])
continue;
for(j=1;j<=p;j++)
if(!vis[j] && a[i][j]!=inf && temp>a[i][j])
temp=a[i][j], j_m=j;
}
len+=temp, vis[j_m]=1;
}
return len;
}
热心网友
时间：2022-06-20 19:48
类似旅行售货员问题？网上应该有这算法吧。
http://hi.baidu.com/sunstar19/blog/item/75f0c0c555fe68c239db49a9.html
热心网友
时间：2022-06-20 19:48
你这题都不会还C++实习。。简单的最小生成树。给个100分说不定帮你打
热心网友
时间：2022-06-20 19:49
O good
