如果你对于问题2理解了的话,会发现分层图中每个点的出度为1可以保证:网络流的答案流中,每个点最多只会被流过1次,即被选择1次.
问题3即点1和n可以被流经无数次,只需将拆点后1->1'和n->n'的边权设为INF,且由于1必为分层图中的底层,故有ST->1=INF;但是n'不一定为分层图的最顶层,所以必须当f[n]==max_len时才能有n'->ed=INF的加边,否则就不加.
by Fish_Clever @ 2022-03-25 20:02:18