花枝喜欢画画，她相信自己能成为一个画家。一天，花枝在自己的小屋子里画了一幅画，
让自己的朋友皮皮龙来欣赏，结果皮皮龙并不喜欢这幅画。花枝感到非常迷惑，
为了改变朋友对她画画技术的观点，花枝给你出了个问题：
在纸上有一些坐标点，每个点都与其他点以线段直接或间接相连，
你的问题便是找出让所有点直接或间接相连最短的距离。
注意，线段的端点只能为原先纸上的坐标点
Input
第一行为坐标的个数， 1<=n<=100。
下面每一行则为每个点的座标，包括两个实数，分别为x座标和y座标。
输入数据中有多个测试案例，程序应处理到数据的结尾。
Output
对于每个测试案例，你的程序应输出使这些点直接或间接相连的最小实数（保留两位小数），每个实数占一行。
Sample Input
3
1.0 1.0
2.0 2.0
2.0 4.0
Sample Output
3.41
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
const int N=110;
double g[N][N];
bool st[N];
double dist[N];
struct node{
double x,y;
}Node[N];
int n;
double prim()
{
memset(dist,0,sizeof dist);
double res=0;
for(int i=1;i<=n;i++)
{
dist[i]=g[1][i];
}
for(int i=1;i<n;i++)
{
int t=-1;
for(int j=2;j<=n;j++)
{
if(!st[j]&&(t==-1||dist[t]>dist[j]))
t=j;
}
res+=dist[t];
st[t]=true;
for(int j=1;j<=n;j++)
{
dist[j]=min(dist[j],g[t][j]);
}
}
return res;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(g,0,sizeof g);
memset(st,false,sizeof st);
for(int i=1;i<=n;i++){
scanf("%lf%lf",&Node[i].x,&Node[i].y);
}
for (int i = 1; i <= n; i ++ )
for (int j = i+1; j <= n; j ++ )
g[i][j] = g[j][i] = sqrt(pow(Node[i].x - Node[j].x, 2) + pow(Node[i].y - Node[j].y, 2));
printf("%.2f\n",prim());
}
return 0;
}
牛子爷得到了一副地图，他想保留图的一些边后让图上的任意两点都能通过这些边互相到达。
他想知道保留这些边的最小花费是多少？边为无向边。
多组输入。每个数据第一行为图中点的个数。紧接着n-1行，
每行的第一个字母为图中的某一个点，（按照字典序升序），
第二个数字表示这个点与比它字典序大的相连点的个数，然后后面紧接着为相连边的花费。
当地图中点的个数为0时，输入结束。
保证可以联通。
Input
多组测试样例，不大于100组
第一行为一个整数n（n大于1且n小于27）。当n=0时输入结束.
接下来n-1行表示边的信息.
Output
每组测试样例输出一个整数，表示最小边花费。
Sample Input
9
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
3
A 2 B 10 C 40
B 1 C 20
0
Sample Output
216
30
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
const int N=30;
int g[N][N];
bool st[N];
int dist[N];
int n;
int prim()
{
memset(dist,0x3f,sizeof dist);
int res=0;
for(int i=0;i<n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
{
if(!st[j]&&(t==-1||dist[t]>dist[j]))
t=j;
}
if(i&&dist[t]==INF)return INF;
if(i)res+=dist[t];
st[t]=true;
for(int j=1;j<=n;j++)
{
dist[j]=min(dist[j],g[t][j]);
}
}
return res;
}
int main()
{
while(scanf("%d",&n))
{
if(n==0)break;
memset(g,0x3f,sizeof g);
memset(st,false,sizeof st);
for(int i=1;i<n;i++)
{
char a[2];
int b;
scanf("%s%d",&a,&b);
char c[2];int d;
for(int j=1;j<=b;j++)
{
scanf("%s%d",&c,&d);
int x=a[0]-'A'+1,y=c[0]-'A'+1;
g[x][y]=g[y][x]=min(g[x][y],d);
}
}
printf("%d\n",prim());
}
return 0;
}
有N个村庄，编号是从1到N，你应该修一些路，这样每两个村庄就可以互相连接。
我们说两个村庄A和B是相连的，当且仅当A和B之间有一条路，或者存在一个村庄C
，使得A和C之间有一条路，C和B是相连的。 我们知道一些村庄之间已经有了一些道路，你的工作是建造一些道路，
这样所有的村庄都是连接的，所有建造的道路的长度都是最小的。
Input
第一行是一个整数N（3 <= N <= 100），它是村庄的数量。然后是N条线，第i条包含N个整数，
这N个整数的第j条是村庄i和村庄j之间的距离（距离应该是[1，1000]以内的整数）
。 然后是一个整数Q（0 <= Q <= N*（N + 1）/ 2）。然后是Q线，
每条线包含两个整数a和b（1 <= a < b <= N），这意味着a村和b村之间的道路已经建成。（注：多组输入）
Output
您应该输出一个包含整数的行，这是所有村庄都连接起来的所有道路的长度，这个值是最小值。
Sample Input
3
0 990 692
990 0 179
692 179 0
1
1 2
Sample Output
179
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
const int N=110;
int g[N][N];
int dist[N];
bool st[N];
int n;
int prim()
{
memset(dist,0x3f,sizeof dist);
int res=0;
for(int i=0;i<n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
{
if(!st[j]&&(t==-1||dist[t]>dist[j]))
t=j;
}
if(i&&dist[t]==INF)return INF;
if(i)res+=dist[t];
st[t]=true;
for(int j=1;j<=n;j++)
{
dist[j]=min(dist[j],g[t][j]);
}
}
return res;
}
int main()
{
while(~scanf("%d",&n))
{
memset(g,0x3f,sizeof g);
memset(st,false,sizeof st);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&g[i][j]);
}
}
int q;
scanf("%d",&q);
int a,b;
while(q--)
{
scanf("%d%d",&a,&b);
g[a][b]=g[b][a]=0;
}
printf("%d\n",prim());
}
return 0;
}
