首页 > 代码库 > UVALive 4035 - Undetectable Tour(并查集)
UVALive 4035 - Undetectable Tour(并查集)
题意:给定一个 N * N(3 <= N <= 10000)的矩形区域,左下角为(0,0),右上角为(N,N),现在要从左下角走到右上角,但是有 k(k <= 100)个监视器,每个监视器的监视范围都是统一的,现给定监视范围可能出现的种类与概率,求能够逃出去的概率。(计算距离时均用曼哈顿距离)
1、若两个监视器的距离 <= 两个监视器的监视范围之和,则这两个监视器间的路就不可走;
2、若监视器距离墙的距离 <= 监视器的监视范围,则监视器与墙之间就不可走;
综上,对于每一个监视范围,可以借助并查集判断是否 "左边界和上边界" 与 "右边界和下边界" 之间不可走,若可走则证明在此监视范围下可以逃出去。
若将监视范围排序,并二分找临界答案,时间将更短。
代码如下:
1 #pragma comment(linker, "/STACK:102400000, 102400000") 2 #include<cstdio> 3 #include<cstring> 4 #include<cctype> 5 #include<cstdlib> 6 #include<cmath> 7 #include<iostream> 8 #include<sstream> 9 #include<iterator> 10 #include<algorithm> 11 #include<string> 12 #include<vector> 13 #include<set> 14 #include<map> 15 #include<deque> 16 #include<queue> 17 #include<stack> 18 #include<list> 19 #define fin freopen("in.txt", "r", stdin) 20 #define fout freopen("out.txt", "w", stdout) 21 #define pr(x) cout << #x << " : " << x << " " 22 #define prln(x) cout << #x << " : " << x << endl 23 #define Min(a, b) ((a < b) ? a : b) 24 #define Max(a, b) ((a < b) ? b : a) 25 typedef long long ll; 26 typedef unsigned long long llu; 27 const int INT_INF = 0x3f3f3f3f; 28 const int INT_M_INF = 0x7f7f7f7f; 29 const ll LL_INF = 0x3f3f3f3f3f3f3f3f; 30 const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f; 31 const double pi = acos(-1.0); 32 const double EPS = 1e-8; 33 const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1}; 34 const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1}; 35 const ll MOD = 1e9 + 7; 36 using namespace std; 37 38 #define NDEBUG 39 #include<cassert> 40 const int MAXN = 100 + 10; 41 const int MAXT = 10000 + 10; 42 43 struct Detector{ 44 int x, y; 45 Detector(int xx = 0.0, int yy = 0.0) : x(xx), y(yy) {} 46 }; 47 48 struct Query{ 49 int radius; 50 double pro; 51 bool operator < (const Query &rhs) const{ 52 return radius < rhs.radius; 53 } 54 }q[MAXN]; 55 56 int T, m, fa[MAXN * 3], n; 57 vector<Detector> vec; 58 59 int Find(int x) { 60 return fa[x] = (fa[x] == x) ? x : Find(fa[x]); 61 } 62 63 inline int get_dist(int x1, int y1, int x2, int y2) { 64 return abs(x1 - x2) + abs(y1 - y2); 65 } 66 67 inline void merge_(int x, int y) { 68 int one = Find(x), two = Find(y); 69 if(one == two) return; 70 if(one < two) fa[two] = one; 71 else fa[one] = two; 72 } 73 74 bool judge(int dist) { 75 for(int i = 0; i < MAXN * 3; ++i) fa[i] = i; 76 int len = (int)vec.size() - 1; 77 for(int i = 1; i <= len; ++i) 78 for(int j = i + 1; j <= len; ++j) { 79 int tmp = get_dist(vec[i].x, vec[i].y, vec[j].x, vec[j].y); 80 if(tmp <= dist * 2) merge_(i, j); 81 } 82 for(int i = 1; i <= len; ++i) { 83 if(vec[i].x <= dist || n - vec[i].y <= dist) merge_(0, i); 84 if(vec[i].y <= dist || n - vec[i].x <= dist) merge_(i, len + 1); 85 } 86 return Find(0) != Find(len + 1); 87 } 88 89 int solve() { 90 int l = 0, r = m - 1; 91 while(l < r) { 92 int mid = l + (r - l + 1) / 2; 93 if(judge(q[mid].radius)) l = mid; 94 else r = mid - 1; 95 } 96 return judge(q[l].radius) ? l : -1; 97 } 98 99 int main(){ 100 // fin; 101 scanf("%d", &T); 102 while(T--) { 103 vec.clear(); 104 vec.push_back(Detector()); 105 scanf("%d%d", &n, &m); 106 for(int i = 0; i < m; ++i) scanf("%d%lf", &q[i].radius, &q[i].pro); 107 sort(q, q + m); 108 int u, v; 109 while(scanf("%d", &u) == 1 && u != -1) { 110 scanf("%d", &v); 111 vec.push_back(Detector(u, v)); 112 } 113 int len = solve(); 114 double ans = 0.0; 115 for(int i = 0; i <= len; ++i) ans += q[i].pro; 116 printf("%g\n", ans); 117 } 118 return 0; 119 }
UVALive 4035 - Undetectable Tour(并查集)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。