如果这道题改成最后到达n号草场怎么做?
查看原帖
如果这道题改成最后到达n号草场怎么做?
248968
wsx248楼主2023/2/8 21:43

MnZn求问,如果改成从1号草场出发,可以逆行1次,最后到达n号草场(或者是任意一个除了1以外的草场),那又该怎么做?

想了下这样做的话,分层图好像就是错误的,会多次重复计算其中一些草场的数量。。

eg:

3 2
1 2
2 3

要求从1号出发到达3号,最多可以经过3个草场(即不反向走),但分层图出来路线是id[1]id[2]id[3]id[2]+sccid[3]+sccid[1]\rightarrow id[2]\rightarrow id[3]\rightarrow id[2]+scc\rightarrow id[3]+scc(idid 是原点对应的强连通分量序号,sccscc 是强连通分量个数),答案会变成 4,可以发现是 id[2]id[2]被多算了一次。

但是跑一次正图一次反图然后做dp的话,状态方程应该是相似的,只是反图的起点改成 id[3]id[3],不过这样算出来也还是4。

求助大佬解惑!!

2023/2/8 21:43
加载中...