Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 实在不知道我是为什么WA了。。

Posted by ydong17 at 2020-03-31 16:43:27 on Problem 2349
```#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<climits>
#include<cstring>

using namespace std;
int N, S, P;

const int INF = INT_MAX;
const int maxp = 500 + 5;
double x[maxp];
double y[maxp];//坐标 有计算距离操作的话，最好采用double
double w[maxp][maxp];//坐标从1开始,邻接矩阵
bool mstSet[maxp];
double Key[maxp];
int parent[maxp];

double dist(int x1, int y1, int x2, int y2) {
double d = sqrt(pow((x1-x2),2)/1.00+pow((y1-y2),2)/1.00);
return d;
}

int minKey(double Key[], bool mstSet[]) {
int min_idx = 0, Min = INF;
for (int u = 1; u <= P; u++) {
if (!mstSet[u] && Key[u] < Min) {
Min = Key[u];
min_idx = u;
}
}
return min_idx;
}

bool cmp(double x, double y) {
if (x < y)return false;
else return true;
}

int main() {
freopen("data_try.txt", "r", stdin);
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%d%d", &S, &P);

//构造邻接矩阵
for (int k = 1; k <= P; k++) {
scanf("%lf%lf", &x[k], &y[k]);
//和前面所有人算一次距离
for (int j = 1; j <=k; j++) {
if (j == k)w[j][k] = 0;
else w[k][j]=w[j][k]=dist(x[j], y[j], x[k], y[k]);//邻接矩阵，权重计算完毕
}
}
//prim算法
memset(mstSet, false, sizeof(mstSet));
for (int j = 1; j <= P; j++) {
Key[j] = INF;
}
Key[1] = 0;//X集合里面，有了第1个点
parent[1] = -1;

double sum = 0;

for (int i = 1; i <= P; i++) {
//要让mstSet包含一个点
int u = minKey(Key, mstSet);
mstSet[u] = true;
sum += Key[u];

for (int j = 1; j <= P; j++) {
if (!mstSet[j] && w[i][j] && w[i][j] < Key[j]) {
Key[j] = w[i][j], parent[j] = i;
}
}
}

//现在把最小生成树的所有边弄到el里面去
vector<double> el;//edge length
for (int i = 1; i <= P; i++) {
if (mstSet[i]) {

if (parent[i] != -1) {
int j = parent[i];
el.push_back(w[i][j]);
}
}
}
int num=el.size();
sort(el.begin(), el.end(), cmp);
printf("%.2f\n", el[S-1]);

}
return 0;
}
```

Followed by: