【题解】[CCO2021] Travelling Merchant

本文主要是介绍【题解】[CCO2021] Travelling Merchant，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

先口胡一个，明天再来补代码（

先考虑 \(-1\) 的情况，显然没有出边的点是 \(-1\)，将这样的点和对应的边删掉，直到每个点都有出边。显然被删掉的点都是 \(-1\)，其余的点都不是 \(-1\)。

对于剩下的边，显然 \(r_i\) 最大的边如果走了，那么其他的边随便走，所以对应的 \(+p_i\) 没有意义。我们直接删掉这条边，然后在起始点 \(a_i\) 打上 \(r_i\) 的标记表示到达这里后且资产 \(\ge\) 标记可以直接结束。

删掉边后 \(a_i\) 可能没有出边了，这又回到 \(-1\) 的情况，将对应的点和边删掉，然后找 \(r_i\) 最大的边删掉。最后将所有边删掉。

每个点的标记就是答案。

这道题的关键在于逆向思维和归纳法，如果顺着模拟非常困难，但是从结束时的边入手则非常清晰。每次删除一条边归纳下去也是关键。

这篇关于【题解】[CCO2021] Travelling Merchant的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！