原文出自:
https://blog.csdn.net/vocaloid01/article/details/76559746
個人非常喜歡這段代碼,不是特别難,但是又新學到了東西。思路還特别清晰。 給這個部落客膜拜了。
有n個城市,你要把他們用隧道連起來,問最少修多少米的隧道。
#include<stdio.h>
#include<cstring>
#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<set>
#include<algorithm>
#include<cmath>
#define INF 0x3f3f3f3f
using namespace std;
struct D //存邊的資訊
{
double len;
int head,tail;
D(int a,int b,double mid)
{
head = a;
tail = b;
len = mid;
}
};
struct cmp
{
bool operator()(D a,D b)
{
return a.len>b.len;
}
};
int pre[105];
int flag;
double board[105][2];
int edge;
double lenth;
int find(int a) //找祖先
{
if(pre[a] == a)return a;
return pre[a] = find(pre[a]);
}
int judge(int a,int b) //判斷是在一個集合
{
int A = find(a);
int B = find(b);
if(A != B)
{
pre[A] = B;
return 1;
}
return 0;
}
int main()
{
int N;
int key = 1;
while(scanf("%d",&N)&&N)
{
if(key)key--;
else printf("\n");//注意格式
lenth = 0;
for(int i=0 ; i<=N ; i++)pre[i] = i;
edge = 0;
priority_queue<D,vector<D>,cmp>Q;
for(int i=0 ; i<N ; i++)
{
scanf("%lf %lf",&board[i][0],&board[i][1]);
}
for(int i=0 ; i<N ; i++)
{
for(int j=i+1 ; j<N ; j++)
{
double len = sqrt(pow((board[i][0]-board[j][0]),2)+pow((board[i][1]-board[j][1]),2));
Q.push(D(i,j,len)); // 把每條邊的資訊計算出來然後入隊
}
}
while(edge < N-1) //找到N-1條邊後結束
{
D mid = Q.top();
Q.pop();
if(judge(mid.head,mid.tail))
{
edge++;
lenth += mid.len;
}
}
printf("Case #%d:\n",++flag);
printf("The minimal distance is: %.2f\n",lenth);
}
return 0;
}