@[Milonia](/user/1061461) 改大了也不行啊，还是40分
by 0x00dream @ 2024-03-14 17:33:53
@[0x00dream](/user/920853) 那可能是别的问题了，要不你发一下代码我看看？
by Milonia @ 2024-03-14 19:07:44
@[Milonia](/user/1061461) ```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
struct Node{
double x,y;
};
struct Edge{
int x,y;
double weight;
};
int father[N];
int height[N];
double Distance(double x1,double y1,double x2,double y2){
double distance;
distance = sqrt(pow(x1-x2,2)+ pow(y1-y2,2));
return distance;
}
void Init(int n){
for (int i = 0; i < n; ++i) {
father[i] = i;
height[i] = 1;
}
}
int Find(int x){
if (father[x] != x)
father[x] = Find(father[x]);
return father[x];
}
void Union(int x,int y,double weight,double &D,int &sum){
int root_x = Find(x);
int root_y = Find(y);
if (root_x != root_y && sum>0){
if (height[root_x] < height[root_y])
father[root_x] = root_y;
else if (height[root_x] > height[root_y])
father[root_y] = root_x;
else if (height[root_x] > height[root_y]){
father[root_x] = root_y;
height[root_y]++;
}
--sum;
}
if (sum == 0)
D = weight;
}
bool comp(Edge lhs,Edge rhs){
return lhs.weight < rhs.weight;
}
vector<Node> myNode;
vector<Edge> myEdge;
int main(){
int S,P; //S个有线电话，P个哨所
scanf("%d%d",&S,&P);
Init(P);
for (int i = 0; i < P; ++i) {
Node node;
scanf("%lf%lf",&node.x,&node.y); //每个结点的坐标
myNode.push_back(node);
}
int edge_min = P-1; //P个哨所的最小生成树有P-1条边
int edge_add = edge_min - (S-1); //现在只有S个有线电话(可以连接S-1条边)，那么还需加多少个无线电话,距离要尽可能的短
for (int i = 0; i < P; ++i) {
Edge edge;
edge.x = i;
for (int j = 0; j < P && j != i; ++j) {
edge.y = j;
edge.weight = Distance(myNode[i].x,myNode[i].y,myNode[j].x,myNode[j].y);
myEdge.push_back(edge);
}
}
double D = DBL_MAX;
sort(myEdge.begin(),myEdge.end(),comp);
for (int i = 0; i < myEdge.size(); ++i) {
Edge edge = myEdge[i];
Union(edge.x,edge.y,edge.weight,D,edge_add);
if (D != DBL_MAX)
break;
}
printf("%.2lf",D);
}
```
by 0x00dream @ 2024-03-14 19:50:20
@[Milonia](/user/1061461)
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
struct Node{
double x,y;
};
struct Edge{
int x,y;
double weight;
};
int father[N];
int height[N];
double Distance(double x1,double y1,double x2,double y2){
double distance;
distance = sqrt(pow(x1-x2,2)+ pow(y1-y2,2));
return distance;
}
void Init(int n){
for (int i = 0; i < n; ++i) {
father[i] = i;
height[i] = 1;
}
}
int Find(int x){
if (father[x] != x)
father[x] = Find(father[x]);
return father[x];
}
void Union(int x,int y,double weight,double &D,int &sum){
int root_x = Find(x);
int root_y = Find(y);
if (root_x != root_y && sum>0){
if (height[root_x] < height[root_y])
father[root_x] = root_y;
else if (height[root_x] > height[root_y])
father[root_y] = root_x;
else if (height[root_x] > height[root_y]){
father[root_x] = root_y;
height[root_y]++;
}
--sum;
}
if (sum == 0)
D = weight;
}
bool comp(Edge lhs,Edge rhs){
return lhs.weight < rhs.weight;
}
vector<Node> myNode;
vector<Edge> myEdge;
int main(){
int S,P; //S个有线电话，P个哨所
scanf("%d%d",&S,&P);
Init(P);
for (int i = 0; i < P; ++i) {
Node node;
scanf("%lf%lf",&node.x,&node.y); //每个结点的坐标
myNode.push_back(node);
}
int edge_min = P-1; //P个哨所的最小生成树有P-1条边
int edge_add = edge_min - (S-1); //现在只有S个有线电话(可以连接S-1条边)，那么还需加多少个无线电话,距离要尽可能的短
for (int i = 0; i < P; ++i) {
Edge edge;
edge.x = i;
for (int j = 0; j < P && j != i; ++j) {
edge.y = j;
edge.weight = Distance(myNode[i].x,myNode[i].y,myNode[j].x,myNode[j].y);
myEdge.push_back(edge);
}
}
double D = DBL_MAX;
sort(myEdge.begin(),myEdge.end(),comp);
for (int i = 0; i < myEdge.size(); ++i) {
Edge edge = myEdge[i];
Union(edge.x,edge.y,edge.weight,D,edge_add);
if (D != DBL_MAX)
break;
}
printf("%.2lf",D);
}
```
by 0x00dream @ 2024-03-14 19:50:49
@[0x00dream](/user/920853)
```cpp
for (int i = 0; i < P; ++i) {
Edge edge;
edge.x = i;
for (int j = 0; j < P && j != i; ++j) {
edge.y = j;
edge.weight = Distance(myNode[i].x,myNode[i].y,myNode[j].x,myNode[j].y);
myEdge.push_back(edge);
}
}
```
你看一下这里的第二重循环，如果i!=j的话就直接退出循环了，应该在循环里面写一个if判断一下如果i==j 就continue
你这样改一下试试
by Milonia @ 2024-03-15 12:34:47
@[Milonia](/user/1061461) 、
感谢大佬
by 0x00dream @ 2024-03-15 15:57:34