洛谷 P6405 [COCI 2014/2015 #2] ŠUMA 题解

Solution

不难发现我们只需要关心相邻的格子在什么时候相等，仅在相等时连边，然后找出现过的最大连通块。
设两个相邻格子分别为 \((i_1,j_1)\) 和 \((i_2,j_2)\)，相等时刻为 \(x\)。不难列出方程 \((v_{i_2,j_2}-v_{i_1,j_1})x=h_{i_1,j_1}-h_{i_2,j_2}\)。
设 \(A=h_{i_1,j_1}-h_{i_2,j_2}\)，\(B=v_{i_2,j_2}-v_{i_1,j_1}\)。

• 若 \(A=0\)，\(B=0\)，则两个格子高度永远相等，连边是永久边。
  
• 若 \(A\neq0\)，\(B=0\)，无解。
  
• 若 \(B\neq 0\)，\(x\) 有唯一解，因此边是瞬时边。注意 \(x\) 必须 \(\ge 0\)。
  

我们先处理出所有边，建一个并查集维护永久边形成的连通块并缩成点。再用第二个并查集维护这些新点之上的连通块。
然后将所有瞬时边按出现时刻排序后，每次将所有同一时刻出现的边加入第二个并查集并更新答案即可。但这样需要多次初始化第二个并查集，这可以用时间戳+懒标记 \(O(1)\) 实现。
浮点数可能会掉精度，最好手写分数存储时刻。
Code

[code]#include #define rep(i,a,b) for(int i(a);i

前排留名，哈哈哈

感谢分享，学习下。

懂技术并乐意极积无私分享的人越来越少。珍惜

yyds。多谢分享

谢谢分享，试用一下

这个有用。

这个有用。

这个好，看起来很实用

这个有用。

感谢分享

热心回复！

鼓励转贴优秀软件安全工具和文档！

感谢分享