230722 做题记录 // 网络流二十四题 (1/24)

知耻而后勇，物极必反。

A. 星际转移问题

http://222.180.160.110:1024/contest/3952/problem/1

如果就按照题目给的路线图，我们显然无法考虑到飞船到达的时刻。同时 \(n\) 和 \(m\) 又很小，我们就知道了，「人不能两次踏进同一条河流」，1 时刻的站 \(p\) 和 2 时刻的站 \(p\) 也不能是同一个站 \(p\)。

考虑用 \((p, t)\) 表示 \(t\) 时刻的站 \(p\)，然后跑个暴力连边，容量全部为 \(1\)。

怎么控制时间最小呢？二分一下就可以了…… 然后最大流判定是不是满流的即可。