思考题 with song

75

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 and Exp , meaning if you are at least levels and are on the same node as the monster, you can beat it and gain levels. You can choose not to beat a monster at a node. You start with lvl

Can you reach node N with at least levels?

Constriants

Standard: N,M<=500.

Lunatic: N,M<=100000

For all,

Solution

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 in the SCC in ascending order. Then we call a monster reachable if . Then for any Y, the last monster we will fight in the SCC is the monster before the first unreachable monster that .

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 . 2. if the previous monster is not reachable and . It can be seen that the second condition is nonsense, because and holds, so always holds.

Then how to find out the first unreachable monster? We can store in a segment tree and do segment tree descend. This task is trivial.

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!