Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
这题的复杂度是O(N ^ 2 + M),因为修理操作最多执行N次,每次检测N - 1个计算机,剩下的只能是判断操作,每一次判断可以看作O( 1 )#include <iostream> #include <math.h> using namespace std; struct Computer { bool repaired;//是否已被修复 int x;//横坐标 int y;//纵坐标 int father;//父节点 int depth;//树的深度 }com[1002]; void unite(int a, int b);//合并操作 int findfather(int a);//查询操作 double getdistance(const int & a, const int & b);//返回 a b 两个节点的距离 int main() { int N, d, p, q;//节点数 最大距离 p q char ope;//操作类型 cin >> N >> d; for (int i = 1; i <= N; i++) { cin >> com[i].x >> com[i].y; com[i].father = i;//将每个节点的父节点初始化为自身 } while (cin >> ope) { if (ope == 'O') { cin >> p; for (int i = 1; i <= N; i++) { if (com[i].repaired) { if (getdistance(i, p) <= d) { unite(i, p); } } } com[p].repaired = true; } else { cin >> p >> q; if (findfather(p) == findfather(q)) { cout << "SUCCESS\n"; } else { cout << "FAIL\n"; } } } return 0; } void unite(int a, int b) { a = findfather(a); b = findfather(b); if (a != b) { if (com[a].depth == com[b].depth) { com[a].father = b; com[b].depth++; } else if (com[a].depth > com[b].depth) { com[b].father = a; } else { com[a].father = b; } } return; } int findfather(int a) { if (com[a].father == a) { return a; } else { return com[a].father = findfather(com[a].father); } } double getdistance(const int & a, const int & b) { static int dx, dy; dx = com[a].x - com[b].x; dy = com[a].y - com[b].y; return sqrt((double)(dx * dx + dy * dy)); } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator