思考题 with song
There have been 73 heroes failing to rescue the princess, and the 74-th was killed by the princess. As the 75-th knight, you decided to become stronger so that you would survive the princess's attack.
You are given a directed graph of N nodes and M edges. The Node #1 is your starting village and Node #N is the princess's castle. On node i there is one monster at Lvl
Can you reach node N with at least
The author can only provide a solution for the standard testset. First do SCC decomposition. In each SCC we will discuss separately.
In each SCC, the process is like this: our knight fights all monsters he can fight, gain some level and repeat the process. If there is no monster he can fight, he will move on to the next SCC. So we need to find out when given the initial level what will the highest level the knight can achieve by walking around in the SCC.
Let's call the initial level Y.And this can be done by sorting all
Proof: For each monster, it can be reached by two ways: 1. if the previous monster(don't forget we have sorted them) is reachable and
Then how to find out the first unreachable monster? We can store
so we can construct a DP function DP(i,j) meaning if we are at the i-th SCC and at level j, what's the maximum level we can achieve when reaching the destination. Don't forget that after SCC Decomposition the graph is already a DAG. So DP works. Transferring is simple, DP(i,j) can move to all its neighbours with DP(nei,getMaxLv(i,j)). and in getMaxLv() we just simply call the segment tree.
Total complexity is O(NMlog) If there are any problems, please comment below. If you have better solutions, you can comment too!