洛谷P2504聪明的猴子

思路：最小生成树

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<vector>
 8 using namespace std;
 9 int n, m;
10 int countx = 0, res[1005];//记录加入的边数,边
11 int nodex[1005][2];
12 //并查集
13 int f[500505] = { 0 };
14 int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
15 void merge(int x, int y) { f[find(x)] = find(y); }//x根连在y的根上
16 void kruskal(vector<vector< int>> x) {
17     for (int i = 1; i < m + 1; i++) {
18         if (find(x[i][1]) != find(x[i][2])) {//判断是否该边两节点已连通
19             merge(x[i][1], x[i][2]);//连通
20             countx++;
21             res[countx] = x[i][0];
22         }
23         if (countx == n - 1) break;//全部连通
24     }
25 }
26 int lengthx(int x1, int y1, int x2, int y2) {
27     return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
28 }
29 int main()
30 {
31     int monkey_num = 0, monkey[505];
32     scanf("%d", &monkey_num);
33     for (int i = 1; i <= monkey_num; i++) scanf("%d", &monkey[i]);
34     sort(monkey + 1, monkey + monkey_num + 1);
35     scanf("%d", &n);
36     for (int i = 1; i <= n; i++) scanf("%d %d", &nodex[i][0],&nodex[i][1]);
37     m = 0;
38     for (int i = 1; i < n; i++) m += i;
39     for (int i = 1; i < m + 1; i++) f[i] = i;   //初始化并查集
40     vector<vector< int>> edge(m + 1, vector<int>(3, 0));
41     int c = 0;
42     for (int i = 1; i < n; i++) {
43         for (int j = i + 1; j <= n; j++) {
44             edge[++c][1] = i;
45             edge[c][2] = j;
46             edge[c][0] = lengthx(nodex[i][0], nodex[i][1], nodex[j][0], nodex[j][1]);
47         }
48     }
49     sort(edge.begin(), edge.end());//按边权值升序排列
50     kruskal(edge);
51     int maxres = 0;
52     for (int i = 1; i < n; i++) maxres = max(res[i], maxres);
53     int ress = 1;
54     while (maxres > monkey[ress] * monkey[ress] && ress <= monkey_num) ress++;
55     printf("%d", monkey_num - ress + 1);
56     return 0;
57 }