代码如下:
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define p pair<int, int>
using namespace std;
const int maxn = 10005;
const int maxm = 10005;
struct edge
{
int x, y;
double w;
};
vector <edge> a;
p tree[maxn];
double cal (p a, p b)
{
return sqrt(pow(a.first - b.first,2) + pow(a.second - b.second, 2));
}
int f[maxn], jump[maxn];
int n, m, cnt;
double ans = 0;
bool cmp(edge x, edge y)
{
return x.w < y.w;
}
void init()
{
for (int i = 0; i <= n; i++)
f[i] = i;
}
int find(int x)
{
if (x == f[x])
return x;
f[x] = find(f[x]);
return f[x];
}
void merge(int x, int y, double w)
{
int fx = find(x);
int fy = find(y);
if (fx != fy)
{
f[fy] = fx;
ans = max(ans, w);
cnt++;
}
}
int main()
{
cin >> n;
// input
for (int i = 1; i <=n; i++)
cin >> jump[i];
cin>>m;
for (int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
// cout<<x<<" "<<y<<endl;
tree[i] = make_pair(x,y);
}
for (int i = 1; i <= m-1; i++)
for (int j = i + 1; j<=m; j++)
{
edge cur = {i,j,cal(tree[i], tree[j])};
a.push_back(cur);
}
sort(a.begin(), a.end(), cmp);
// for (edge e : a)
// cout<<e.x<<" "<<e.y<<" "<<e.w<<endl;
//便利一遍边,merge
init();
for (int i = 0; i < a.size(); i++)
{
merge(a[i].x, a[i].y, a[i].w);
if (cnt == m - 1)
break;
}
long long ret = 0;
for (int i = 1; i<=n; i++)
if (jump[i] >= ans)
ret++;
cout << ret;
return 0;
}
这是提交记录
希望神犇帮我看眼哪出问题了,万分感谢