畅通工程再续
相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖，发展首先要解决的问题当然是交通问题，政府决定实现百岛湖的全畅通！经过考察小组RPRush对百岛湖的情况充分了解后，决定在符合条件的小岛间建上桥，所谓符合条件，就是2个小岛之间的距离不能小于10米，也不能大于1000米。当然，为了节省资金，只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。
Input
输入包括多组数据。输入首先包括一个整数T(T <= 200)，代表有T组数据。
每组数据首先是一个整数C(C <= 100),代表小岛的个数，接下来是C组坐标，代表每个小岛的坐标，这些坐标都是 0 <= x, y <= 1000的整数。
Output
每组输入数据输出一行，代表建桥的最小花费，结果保留一位小数。如果无法实现工程以达到全部畅通，输出”oh!”.
Sample Input
2 2 10 10 20 20 3 1 1 2 2 1000 1000
Sample Output
1414.2 oh!
C++版本一
参考https://blog.csdn.net/weixin_43272781/article/details/83588706
最小生成树，用kruskal求解,此题特别之处，给出的位置是坐标的形式，需把它转化为求最小生成树的一般位置形式。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
const int N=10000+10;
int t,n,m,pre[N];
struct node{
int x,y;
node(){};
node(int a, int b){
x=a;
y=b;
}
}point[N];
double L(int x,int y,int x2,int y2){
return sqrt(abs((x-x2)*(x-x2)+(y-y2)*(y-y2)));
}
struct Edge{
int f,t;
double l;
Edge(){};
Edge(int a, int b,double c){
f=a;
t=b;
l=c;
}
bool operator <(const Edge &S)const{
return l<S.l;
}
}e[N];
int find(int x){
int r=x;
while(pre[r]!=r)
r=pre[r];
return r;
}
void join(int x,int y){
int fx=find(x);
int fy=find(y);
if(fx!=fy)
pre[fx]=fy;
}
int main()
{
scanf("%d",&t);
while(t--){
scanf("%d",&n);
int a,b;
for(int i=1;i<=n;i++){
scanf("%d%d",&a,&b);
point[i]=node(a,b);
}
int cnt=0;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
e[++cnt]=Edge(i,j,L(point[i].x,point[i].y,point[j].x,point[j].y));
}
}
sort(e+1,e+cnt+1);
for(int i=1;i<=n;i++){
pre[i]=i;
}
double ans=0;
for(int i=1;i<=cnt;i++)
if(find(e[i].f)!=find(e[i].t)&&e[i].l>=10.0&&e[i].l<=1000.0){
join(e[i].f,e[i].t);
ans+=e[i].l;
}
int cn=0;
for(int i=1;i<=n;i++)
if(pre[i]==i)
cn++;
if(cn-1==0)
printf("%.1lf\n",ans*100);
else
cout << "oh!" << endl;
}
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
//HDU 1875 AC
#include <iostream>
#include <cmath>
using namespace std;
#define MAX 100010
#define LEN 105
double dist[LEN];
double map[LEN][LEN];
bool isvisited[LEN];
//点的结构体
typedef struct Point{
double x;
double y;
}Point;
//初始化
void init(){
int i,j;
for(i=0;i<LEN;i++){
for(j=0;j<LEN;j++){
if(i==j) map[i][j]=0; //对a[][]进行初始化，一般都要；
map[i][j]=MAX;
}
}
}
//计算两点距离
double caculteD(Point a,Point b){
double len;
len=sqrt(1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y));
return len;
}
//prim算法
double prim(int n){
int i,j,min,pos;
double sum=0;
memset(isvisited,false,sizeof(isvisited));
//初始化
for(i=1;i<=n;i++){
dist[i]=map[1][i];
}
//从1开始
isvisited[1]=true;
dist[1]=MAX;
//找到权值最小点并记录下位置
for(i=1;i<n;i++){
min=MAX;
//pos=-1;
for(j=1;j<=n;j++){
if(!isvisited[j] && dist[j]<min){
min=dist[j];
pos=j;
}
}
if(min==MAX){
return -1;
}
sum+=dist[pos];//加上权值
isvisited[pos]=true;
//更新权值
for(j=1;j<=n;j++){
if(!isvisited[j] && dist[j]>map[pos][j]){
dist[j]=map[pos][j];
}
}
}
return sum;
}
int main(){
Point p[105];
int i,j,n,nCase;
cin>>nCase;
double result;//总价
while(nCase--){
cin>>n;
init(); //初始化
for(i=1;i<=n;i++){
scanf("%lf%lf",&p[i].x,&p[i].y);
}
for(i=1;i<n;i++){
for(j=i+1;j<=n;j++){
double len;
len=caculteD(p[i],p[j]);
if(len>=10 && len<=1000){//长度有限制
map[i][j]=map[j][i]=100*len;//要*100
}
}
}
result=prim(n);
if(result==-1){
cout<<"oh!"<<endl;
}
else{
printf("%.1lf\n",result);
}
}
return 0;
}
C++版本三
这道题做了好久 主要是问题在于 浮点数的处理。
刚开始做意识到 肯定用浮点数来存值 ，但将所有变量都用 浮点数定义时
使用memset 函数对Map 数组初始化为最大时 结果发生了变化
总之 只要处理好 浮点数的关系 其实这道题还是挺容易的
#include <iostream>
#include <cstring>
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
double Map[1005][1005],dis[1005];
int M,visit[1005],flag;
struct node
{
double x, y;
}st[1005];
void prim()
{
flag=0;
for(int i = 1;i <= M; i++)
{
dis[i] = Map[i][1];
}
dis[1] = 0;
visit[1] = 1;
double sum = 0.0;
for(int i = 1; i <= M-1; i++)
{
double temp = INF;
int pos;
for(int j= 1; j <= M; j++)
{
if(!visit[j] && temp > dis[j])
{
temp = dis[j];
pos = j;
}
}
if(temp == INF)
{
flag = 1;
break;
}
sum += dis[pos];
visit[pos] = 1;
for(int j = 1; j <= M; j++)
{
if(!visit[j] && Map[pos][j] < dis[j] && Map[pos][j]!=INF)
{
dis[j] = Map[pos][j];
}
}
}
if (!flag)
printf("%.1lf\n",sum*100.0);
else
printf ("oh!\n");
}
int main()
{
int N;
scanf("%d",&N);
while (N--)
{
memset(visit,0,sizeof(visit));
scanf("%d",&M);
for(int i=1;i<=M;i++)
{
for(int j=1;j<=M;j++)
{
if(i==j)
Map[i][j]=0;
else
Map[i][j]=INF;
}
}
for (int i=1; i<=M; i++)
{
scanf("%lf %lf",&st[i].x,&st[i].y);
for (int j=1; j<i; j++)
{
double dis = sqrt((st[i].x-st[j].x)*(st[i].x-st[j].x)+(st[i].y-st[j].y)*(st[i].y-st[j].y));
if (dis<Map[i][j]&&dis>=10&&dis<=1000)
{
Map[i][j] = Map[j][i] = dis;
}
}
}
prim();
}
}
