MnZn求问,如果改成从1号草场出发,可以逆行1次,最后到达n号草场(或者是任意一个除了1以外的草场),那又该怎么做?
想了下这样做的话,分层图好像就是错误的,会多次重复计算其中一些草场的数量。。
eg:
3 2
1 2
2 3
要求从1号出发到达3号,最多可以经过3个草场(即不反向走),但分层图出来路线是id[1]→id[2]→id[3]→id[2]+scc→id[3]+scc(id 是原点对应的强连通分量序号,scc 是强连通分量个数),答案会变成 4,可以发现是 id[2]被多算了一次。
但是跑一次正图一次反图然后做dp的话,状态方程应该是相似的,只是反图的起点改成 id[3],不过这样算出来也还是4。
求助大佬解惑!!