调代码

Register_int · 2023-06-11 16:06:26 · 休闲·娱乐

近几个月在研究一道图论问题，很难，一直没研究出来。题解全都交过一遍了，没一个能保证正确性的。

现在我的代码基于一个神秘结论，还没来得及证明。手造数据表现得非常好，但是交上去总是差 #8 这一个点。

下了一组 hack 数据，点数居然只有 50。这么小的数据量能把我结论搞崩？这题是个 ds，大致题意是维护有向图，支持恢复一个点连接的边、加边还有删边啥的，求的东西太神秘记不清了。跟着过程模拟了有十几遍，终于发现了问题：最后加入的一个点，自己构成了一个 scc。怎么回事？不是保证全图是一个 scc 吗？数据错了？

回头再看看操作，我发现大部分操作都是将这个点与其它点连边，但不出二十步就又被删除。有时数据还会发疯似的连上数十条重边，还是雨露均沾地连。什么出题人会丧心病狂地搞出这种数据？

思考良久，我决定直接忽略这个点的存在。但仍然出错。它这一疯狂的举措，似乎让点与点之间的联系更加密切。这些点还会尝试连反向边，与它构成一个 scc。当然，都是以失败告终。连边的次序总是差那么一点。差这么一点，它们之间就强连通了。

我决定对数据进行深挖。图里还有三个点的连边方式及其奇怪，它们似乎与所有点都有联系，既有单向边，也有双向边。但它们连接最后一个加入的点时，仍是出奇的一致：不到七步就断开。这也导致最后一个点上的答案总是飘忽不定，令人恼火。

现在，我终于找到了解决方法。修改结论，忽略对这个点的所有入边，再往上加上个固定的参数。但那个点在最后一步时，结果也会出错，变为 -\inf。我不得不对它进行手动修改。

终于通过了那题。迫不及待地写完题解，却被打回。仔细一看，原来题解区全是这种做法。只不过，最后一个点修改的值各不相同。然而这并不是一道 SPJ 题目，其中的原理我可能也搞不懂了。

哦，要求的值好像叫快乐指数还是啥的，不重要。