C++博客-JUST ENJOY! JUST AC!-最新评论http://www.cppblog.com/tortoisewu/CommentsRSS.aspxAcceptedzh-cnFri, 09 Apr 2010 14:33:50 GMTFri, 09 Apr 2010 14:33:50 GMTcnblogsre: poj 1182 解题报告http://www.cppblog.com/tortoisewu/archive/2010/04/05/85501.html#111697monday41monday41Mon, 05 Apr 2010 13:03:00 GMThttp://www.cppblog.com/tortoisewu/archive/2010/04/05/85501.html#111697void unions(int rootx, int rooty, int x, int y, int dkind)
{
if(rank[rootx]>rank[rooty])
{
ufind[rooty].parent=rootx;
rank[rootx]+=rank[rooty];
}
else
{
ufind[rootx].parent=rooty;
rank[rooty]+=rank[rooty];
}
ufind[rooty].kind=(-dkind+(ufind[x].kind-ufind[y].kind)+3)%3;
}

monday41 2010-04-05 21:03 发表评论
]]>re: poj 1182 解题报告http://www.cppblog.com/tortoisewu/archive/2010/02/01/85501.html#106919匿名匿名Sun, 31 Jan 2010 17:25:00 GMThttp://www.cppblog.com/tortoisewu/archive/2010/02/01/85501.html#106919

匿名 2010-02-01 01:25 发表评论
]]>re: 双向广度优先搜索方法(在做完poj 1915后总结的)http://www.cppblog.com/tortoisewu/archive/2010/01/12/86123.html#105508huangzhifeihuangzhifeiTue, 12 Jan 2010 12:40:00 GMThttp://www.cppblog.com/tortoisewu/archive/2010/01/12/86123.html#105508不过1楼的问题，我也想问！

huangzhifei 2010-01-12 20:40 发表评论
]]>re: poj 1182 解题报告http://www.cppblog.com/tortoisewu/archive/2009/10/08/85501.html#98076blackstarblackstarThu, 08 Oct 2009 03:40:00 GMThttp://www.cppblog.com/tortoisewu/archive/2009/10/08/85501.html#98076

blackstar 2009-10-08 11:40 发表评论
]]>re: poj 1182 解题报告[未登录]http://www.cppblog.com/tortoisewu/archive/2009/09/15/85501.html#96209chrischrisTue, 15 Sep 2009 05:11:00 GMThttp://www.cppblog.com/tortoisewu/archive/2009/09/15/85501.html#96209

chris 2009-09-15 13:11 发表评论
]]>re: 双向广度优先搜索方法(在做完poj 1915后总结的)http://www.cppblog.com/tortoisewu/archive/2009/07/15/86123.html#90173futurefutureWed, 15 Jul 2009 13:38:00 GMThttp://www.cppblog.com/tortoisewu/archive/2009/07/15/86123.html#90173
初始化起始点start.step=true; //这里step属性为真则表示为某一搜索步数中的最后一个点,例如对于poj1915中第2步有八个点，只有第八个点的step为true,其余为false

这句语句的作用？

future 2009-07-15 21:38 发表评论
]]>re: poj 1182 解题报告http://www.cppblog.com/tortoisewu/archive/2009/07/14/85501.html#90042GuestGuestTue, 14 Jul 2009 08:10:00 GMThttp://www.cppblog.com/tortoisewu/archive/2009/07/14/85501.html#90042 count++;
条件应该是 (ufind[x].kind-ufind[y].kind+3)%3 != 2 吧

0->1->2->0 吃的关系相差 -1 或 2， 取模后是 2
建议楼主看一下

Guest 2009-07-14 16:10 发表评论
]]>re: poj 1182 解题报告http://www.cppblog.com/tortoisewu/archive/2009/05/30/85501.html#86210tortoisewutortoisewuSat, 30 May 2009 14:28:00 GMThttp://www.cppblog.com/tortoisewu/archive/2009/05/30/85501.html#86210先说下合并函数中的关系，因为在合并函数之前先进行了查找函数，而在查找函数中已压缩了路径，即把查找的点到根结点路径上所有点都挂到了根结点下，并更新了它们kind的值，保证kind值是正确的(在这之前是不正确的)；所以在合并函数中x,y,rootx,rooty的kind值在它们原先的集合中都是正确的，在合并时，要将rooty挂到rootx上，并只更新rooty的kind值以保证rooty在新的集合中kind值正确，而不必管rooty原先集合的其它结点kind值(没法管，因为并查集只能从叶节点遍历到根结点，无法向下遍历，将会放到find函数中更新)。更新的依据是三个关系：x和y的关系，x和rootx关系，y和rooty关系；对于这题就一定能得到rootx和rooty的关系，以更新对rooty在新的集合中的kind值。
如果你能理解了合并函数，那查找函数便可以推得，因为我们合并时只更新了挂在根结点上的原先集合根结点的kind值，所以这里要把查找路径上所有的点先挂到根结点上，并更新其kind值(也就是每个集合深度为1的结点的kind值都是正确的)。更新顺序一定要是从深度低的到深度高的,因为更新依据要依赖当前结点的原kind值和其父节点的更新后的kind值。为什么是上述给出的两个值的和的关系呢?因为在合并前根结点的kind都为0，所以合并后原被合并集合深度为1的点的kind值只要加上更新后原其根结点的kind值就能得到正确关系了。一定要画图理解，模拟下过程，结合我红色标识的三个式子一起理解。我还有篇总结也许有帮助http://www.cppblog.com/tortoisewu/archive/2009/05/29/86110.html@whr


tortoisewu 2009-05-30 22:28 发表评论
]]>re: poj 1182 解题报告http://www.cppblog.com/tortoisewu/archive/2009/05/30/85501.html#86192whrwhrSat, 30 May 2009 11:23:00 GMThttp://www.cppblog.com/tortoisewu/archive/2009/05/30/85501.html#86192

whr 2009-05-30 19:23 发表评论
]]>re: poj 1182 解题报告http://www.cppblog.com/tortoisewu/archive/2009/05/23/85501.html#85503E剑仙E剑仙Sat, 23 May 2009 05:30:00 GMThttp://www.cppblog.com/tortoisewu/archive/2009/05/23/85501.html#85503

E剑仙 2009-05-23 13:30 发表评论
]]>