本文主要是介绍HDU 1875 Prim+并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*这个题目同时用到了并查集和最小生成树用并查集判断所有点是否符合条件在利用最短路计算最小价值
*/#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int Maxn = 1000000;
const int maxn = 105;
double dis[maxn][maxn], cost[maxn], dist;
int vis[maxn], n;struct Point//建立结构体Point来保存点的坐标
{double x, y;
} p[maxn];double Compute(double x1, double y1, double x2, double y2)//计算两点之间距离的函数
{return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}int Find(int t)
{if(vis[t] != t)vis[t] = Find(vis[t]);return vis[t];
}void Merge(int a, int b)//并查集函数，将属于同一个集合的点放在同一个集合中
{int x, y;x = Find(a);y = Find(b);if(x < y) vis[y] = x;else vis[x] = y;
}void Prim()//最短路函数
{cost[1] = 0;for(int i = 2; i <= n; i++)cost[i] = dis[1][i];int temp, m;for(int i = 2; i <= n; i++){temp = Maxn;m = 0;for(int j = 1; j <= n; j++){if(cost[j]<temp && cost[j]!=0){temp = cost[j];m = j;}}dist += cost[m];cost[m] = 0;for(int j = 1; j <= n; j++){if(cost[j] > dis[m][j])cost[j] = dis[m][j];}}
}int main()
{int t;cin >> t;while(t--){dist = 0;cin >> n;for(int i = 1; i <= n; i++){cin >> p[i].x >> p[i].y;vis[i] = i;}for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++){double d = Compute(p[i].x,p[i].y,p[j].x,p[j].y);if(d>=10 && d<=1000)//将满足条件的距离乘以100以费用的形式保存在dis数组中{dis[i][j] = dis[j][i] = d*100;Merge(i,j);//将能够连接在一起的结点合并到一个集合中}else dis[i][j] = dis[j][i] = Maxn;//将距离小于10或者大于1000的两点距离剔除}int cont = 0;for(int i = 1; i <= n; i++)//统计集合的个数if(vis[i] == i) cont++;if(cont != 1)//只有集合个数为1时才能将所有的点连接起来{cout << "oh!" << endl;continue;}Prim();printf("%.1lf\n",dist);}return 0;
}
这篇关于HDU 1875 Prim+并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
