題意

一個計算機網絡里的計算機都壞了, 現在有兩種操作, “O p”代表修復了p機器, “S p q”代表檢查 p, q 兩臺機器是否連接( 直線距離<=d或者中間有距離<=d的用來聯通的機器 )

思路

比賽的時候愣是沒讀清楚題目意思, 還以為是什么搜索, 瞎瘠薄做了個MLE
沒料到居然是個并查集, 注意應該是直線距離 <= d, 不是上下左右走的
每次修復一個機器的時候檢查他與其他機器的直線距離, 并將其并入集合中
查找的時候尋找根節點就ojbk

讀題沒讀明白是一方面, 總的來說還是做題經驗不夠

AC代碼

#include <iostream> #include <cstdio> #include <cstring> #include <cmath>using namespace std; const int maxn = 1e3 + 5; int mrk[maxn]; int n, d; char op[2]; struct computer{int f;int x, y; }p[maxn];void init(){for( int i = 1; i <= maxn; i++ )p[i].f = i;return; }int _find( int a ){if( a != p[a].f )return _find(p[a].f);return a; }double getdis( int x1, int y1, int x2, int y2 ){double dx = fabs((double)(x1-x2));double dy = fabs((double)(y1-y2));double dis = sqrt(dx*dx+dy*dy);return dis; }void _union( const computer a, const computer b ){int aa = _find(a.f);int bb = _find(b.f);if( aa != bb )if( getdis(a.x, a.y, b.x, b.y) <= d )p[bb].f = aa;return; }int main() {int a, b;init();scanf("%d%d",&n, &d);for( int i = 1; i <= n; i++ ){scanf("%d%d", &p[i].x, &p[i].y);}while( ~scanf("%s",op) ){if( op[0] == 'O' ){scanf("%d",&a);mrk[a] = 1;for(int i = 1; i <= n; i++)if( mrk[i] && i != a)_union(p[i], p[a]);}else if( op[0] == 'S' ){scanf("%d%d",&a, &b);if( _find(a) == _find(b) ) puts("SUCCESS");else puts("FAIL");}}return 0; }

轉載于:https://www.cnblogs.com/JinxiSui/p/9740566.html

總結

以上是生活随笔為你收集整理的POJ 2236 - Wireless Network ( 并查集 )的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。