题目描述
在平面直角坐标系内有n个点。现在有m个人,每个人都有一个行走距离d,也就是说这个人只能走到与它当前位置距离不大于d的点。问有多少个人可以从任意一个点开始,并能够到达所有点。
思路
因为题目要求我们每一个点都要走到,所以我们可以用最小生成树来解决
选出最小生成树中的最长边来进行判断即可
这里用的是克鲁斯卡尔+并查集来写的最小生成树,用prime的优化貌似会快很多
#include#include #include using namespace std; #define maxn 1001 #define maxm 1000001 struct edge { int from, to; double w; }e[maxm]; struct arr { int x, y; }b[maxn]; int f[maxn], a[maxn]; int cmp(edge a, edge b) { return a.w < b.w; } int find(int x) { if (!f[x]) return x; f[x] = find(f[x]); return f[x]; } int insert(int x, int y) { if (find(x) != find(y)) { f[find(x)] = find(y); return 1; } return 0; } int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); int m; scanf("%d", &m); for (int i = 1; i <= m; i++) scanf("%d%d", &b[i].x, &b[i].y); int l = 0; for (int i = 1; i <= m; i++) for (int j = i + 1; j <= m; j++) { e[++l].from = i; e[l].to = j; e[l].w = sqrt((b[i].x - b[j].x) * (b[i].x - b[j].x) + (b[i].y - b[j].y) * (b[i].y - b[j].y)); } sort(e + 1, e + l + 1, cmp); double max = 0.0; int tot = 0; for (int i = 1; i <= l; i++) { if (find(e[i].from) != find(e[i].to)) { tot++; max = e[i].w; insert(e[i].from, e[i].to); } } int ans = 0; for (int i = 1; i <= n; i++) if (a[i] * 1.0 >= max) ans++; printf("%d\n", ans); }
]]>
Comments NOTHING