关于阈值的位置影响答案的分析(已过)
查看原帖
关于阈值的位置影响答案的分析(已过)
378678
mimiyou楼主2021/10/21 16:49
1.当拓扑排序遍历到一个点的时候,是不会重复遍历的,看见有的人写的代码是用了一个vis数组,在放入队列的时候才减去,实际上拓扑排序本身并不会重复遍历一个点,所以,这跟在读取数据的时候直接减去阈值是一样的!
2.但是,这在初始位置直接减去阈值确实是会wa掉,根本逻辑是:作为所有遍历到达的点,都直接减去一次阈值【关键在于,这个遍历到达的点并不包括输入点,也就是入度为0的点,而且,题意且样例给定的输入点的阈值都是0,大家都默认了这个“输入点的阈值为0”的条件,但是实际上并不是,而且题本身也没有明确给定,所以,在初始放入队列的时候再加回来一次阈值即可ac(在读入数据的时候对“ci^0”分支一下读取也可避免这个问题)】
3.顺便就再说一点吧,还有一个wa点是,在遍历的时候,对于ci<0的点也要去遍历,减去与它相连的点的入度,否则遍历会不完全。
4.最后,看见讨论区一堆人不懂装懂,给不出有效问题分析,还把问题误导给减去阈值的位置,给我整破防了好吧!
2021/10/21 16:49
加载中...