Timus 1392

系统 1606 0
      
        #include 
      
      
        <
      
      
        iostream
      
      
        >
      
      
        
using namespace std;

typedef
struct ufs_elem_st {
struct ufs_elem_st * next, * prev;
struct ufs_elem_st * parent;
} ufs_elem_st,
* ufs_elem_t;

typedef
struct ufs_st {
ufs_elem_st
* roots;
} ufs_st,
* ufs_t;

typedef
struct star_st {
ufs_elem_st ufs_elem;
int x,y,z,r;
} star_st,
* star_t;

int K;
short star_idx[ 1001 ] = { 0 };
star_st stars[
1001 ] = { 0 };

ufs_elem_t ufs_get_root(ufs_elem_t me) {
ufs_elem_t my_root
= me;
while ( my_root -> parent != my_root && my_root -> parent != NULL )
my_root
= my_root -> parent;

me
-> parent = my_root; // 路径压缩
return my_root;
}

void ufs_add_root(ufs_t ufs, ufs_elem_t me) {
ufs_elem_t my_root
= ufs_get_root(me);
if ( NULL != ufs -> roots ) {
my_root
-> next = ufs -> roots;
ufs
-> roots -> prev = my_root;
}
ufs
-> roots = my_root;
my_root
-> prev = NULL;
}

void ufs_join(ufs_t ufs, ufs_elem_t friend_elem, ufs_elem_t me) {
ufs_elem_t my_root
= ufs_get_root(me);
ufs_elem_t friend_root
= ufs_get_root(friend_elem);
ufs_elem_t final_root
= NULL;

if ( NULL != my_root -> next )
my_root
-> next -> prev = my_root -> prev;
if ( NULL != my_root -> prev )
my_root
-> prev -> next = my_root -> next;
if ( ufs -> roots == my_root )
ufs
-> roots = my_root -> next;
my_root
-> next = my_root -> prev = NULL;

if ( NULL != friend_root -> next )
friend_root
-> next -> prev = friend_root -> prev;
if ( NULL != friend_root -> prev )
friend_root
-> prev -> next = friend_root -> next;
if ( ufs -> roots == friend_root )
ufs
-> roots = friend_root -> next;
friend_root
-> next = friend_root -> prev = NULL;

// 合并集合
star_t s1 = (star_t)my_root, s2 = (star_t)friend_root;
// 根据star的编号决定谁作为集合的代表,这方便最后根据集合中最小的索引号来排序集合
if ( s1 - stars < s2 - stars ) {
friend_root
-> parent = my_root;
final_root
= my_root;
}
else {
my_root
-> parent = friend_root;
final_root
= friend_root;
}

if ( NULL != ufs -> roots ) {
final_root
-> next = ufs -> roots;
ufs
-> roots -> prev = final_root;
}
ufs
-> roots = final_root;
}

bool check(star_t s1, star_t s2) {
int distSquare = (s1 -> x - s2 -> x) * (s1 -> x - s2 -> x) + (s1 -> y - s2 -> y) * (s1 -> y - s2 -> y) + (s1 -> z - s2 -> z) * (s1 -> z - s2 -> z);
int r1r2Square = (s1 -> r + s2 -> r) * (s1 -> r + s2 -> r);
if ( distSquare < r1r2Square )
return true ;
else
return false ;
}

int set_id_cmp( const void * i1, const void * i2) {
ufs_elem_t e1
= (ufs_elem_t)(stars + * ( short * )i1);
ufs_elem_t e2
= (ufs_elem_t)(stars + * ( short * )i2);
return ufs_get_root(e1) - ufs_get_root(e2);
}

int set_elem_id_cmp( const void * i1, const void * i2) {
return * ( short * )i1 - * ( short * )i2;
}

void print_set_elem( int start, int len) {
int i;
len
-- ;
for (i = 0 ;i < len;i ++ )
cout
<< star_idx[start + i] << " , " ;
cout
<< star_idx[start + i] << endl;
}

int main() {
int i,j,k;
bool find_grp;
ufs_st ufs
= { 0 };
cin
>> K;
for ( i = 0 ;i < K;i ++ )
cin
>> stars[i].x >> stars[i].y >> stars[i].z >> stars[i].r;

for ( i = 0 ;i < K;i ++ ) {
for ( j = i + 1 ;j < K;j ++ ) {
if ( ufs_get_root((ufs_elem_t)(stars + i)) == ufs_get_root((ufs_elem_t)(stars + j)) ) // 都一个集合了,不处理
continue ;
// 相连, 把对方假如到我的集合中,谁当集合代表取决于对方的集合代表的编号和我的集合代表的编号
if ( check(stars + i, stars + j) == true )
ufs_join(
& ufs, (ufs_elem_t)(stars + i), (ufs_elem_t)(stars + j));
}
}

for ( i = 0 ;i < K;i ++ )
star_idx[i]
= i;

// 根据集合代表的编号大小来排序集合元素,确保了属于同一个集合的元素都在连续空间
// 集合之间按集合代表的编号排序
qsort(star_idx, K, sizeof ( short ), set_id_cmp);

for ( i = 0 ,j = 1 ,k = 0 ;i < K - 1 ;i ++ ) {
// i 与 i+1 属于同一个集合
if ( ufs_get_root((ufs_elem_t)(stars + star_idx[i])) == ufs_get_root((ufs_elem_t)(stars + star_idx[i + 1 ])) ) {
j
++ ;
}
else { // 不属于同一个集合
// 对一个集合的元素排序,根据元素之间的编号
qsort(star_idx + k, j, sizeof ( short ), set_elem_id_cmp);
print_set_elem(k, j);
j
= 1 ; // 新一个集合的元素个数初始化
k = i + 1 ; // 新一个集合的第一个元素的位置
}
}
qsort(star_idx
+ k, j, sizeof ( short ), set_elem_id_cmp);
print_set_elem(k, j);

return 0 ;
}

刚开始以为是图论的求强连通子图,后来发现也没必要,就是不断地把符合条件的元素加在一起形成集合,刚好是并查集的经典应用。

不过题目在输出顺序要求上带了些难度,所以在并查集的合并过程中做了些改动。

这代码除了并查集,另一个有趣的地方是怎样把算法数据结构和逻辑数据结构结合起来应用,模仿LINUX内核的数据结构。

Timus 1392


更多文章、技术交流、商务合作、联系博主

微信扫码或搜索:z360901061

微信扫一扫加我为好友

QQ号联系: 360901061

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描下面二维码支持博主2元、5元、10元、20元等您想捐的金额吧,狠狠点击下面给点支持吧,站长非常感激您!手机微信长按不能支付解决办法:请将微信支付二维码保存到相册,切换到微信,然后点击微信右上角扫一扫功能,选择支付二维码完成支付。

【本文对您有帮助就好】

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请用微信扫描上面二维码支持博主2元、5元、10元、自定义金额等您想捐的金额吧,站长会非常 感谢您的哦!!!

发表我的评论
最新评论 总共0条评论