Problem Description
某省调查乡村交通状况&＃xff0c;得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通&＃xff08;但不一定有直接的公路相连&＃xff0c;只要能间接通过公路可达即可&＃xff09;&＃xff0c;并要求铺设的公路总长度为最小。请计算最小的公路总长度。
Input
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( <100 )&＃xff1b;随后的N(N-1)/2行对应村庄间的距离&＃xff0c;每行给出一对正整数&＃xff0c;分别是两个村庄的编号&＃xff0c;以及此两村庄间的距离。为简单起见&＃xff0c;村庄从1到N编号。
当N为0时&＃xff0c;输入结束&＃xff0c;该用例不被处理。
Output
对每个测试用例&＃xff0c;在1行里输出最小的公路总长度。
Sample Input
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0
Sample Output
3
5
#include#include#include#define MIN 999999999
#define MAX_Point 120 //最大顶点数
#define MAX_Edge 14400 //最大边数
double arr_list[MAX_Point][MAX_Point];//开边的权值数组
struct edge
{
int point;
double lowcost;
int flag;
}Edge[MAX_Edge];
using namespace std;
double prim(int n)
{
int i,j,k,flag;
double min,sum&＃61;0;
j&＃61;1;
for(i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
{
if(i!&＃61;j)
{
Edge[i].point&＃61;i;
Edge[i].lowcost&＃61;arr_list[j][i];
Edge[i].flag&＃61;0;
}
}
Edge[j].flag&＃61;1;//判断该点是否已经被选择
Edge[j].lowcost&＃61;0;
for(i&＃61;2;i<&＃61;n;i&＃43;&＃43;)
{
k&＃61;1;
flag&＃61;0;
min&＃61;MIN;
for(j&＃61;2;j<&＃61;n;j&＃43;&＃43;)
{
if(Edge[j].flag&＃61;&＃61;0&&Edge[i].lowcost>m)
{
if(m&＃61;&＃61;0)
break;
for(int i&＃61;0;i<&＃61;m;i&＃43;&＃43;)
{
for(int j&＃61;0;j<&＃61;m;j&＃43;&＃43;)
{
arr_list[i][j]&＃61;MIN;
}
}
for(int i&＃61;1;i<&＃61;m*(m-1)/2;i&＃43;&＃43;)
{
cin>>a>>b>>data;
if(data
![扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]](https://img.php1.cn/3c972/245b5/42f/19446f78530d3747.jpeg)
京公网安备 11010802041100号