思考题 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

Can you reach node N with at least

# 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 *reachable* if

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!