最短路状物，最多只会走 $1000$ 天，$f_{u,t}$ 表示在第 $t$ 天走到 $u$ 的最大价值，有向无环图，跑什么都行。

时间复杂度 $\Theta(nT)$。

直接上二分图，显然 $i \to i$ 是一组最大匹配，然后取消 $i$ 的配对，在建的图上跑就得到了 $i$ 的答案，时间复杂度玄学。

连边后发现 $i$ 想要得到 $j$，必须形成一个环执行轮换，直接 floyd 传递闭包即可。时间复杂度 $\Theta(\frac{n^3}{\omega})$。

口胡。

两个点能换说明在同一个强连通分量中，直接 $\Theta(n+m)$ 跑 tarjan。等待验证。

对每个店 $i$ 计算以它为直角顶点的答案，贡献是

对于 $x$ 坐标相同和 $y$ 坐标相同的放入一个集合，预处理前缀后缀和。

时间复杂度 $\Theta(n\log n)$。