首先不难想到BFS。

以及，箱子能被推动到目标方向当且仅当：①目标方向是空地；②目标方向关于箱子的对面是空地，且人能到达。

如果允许人在空地上任意传送，本题将会简单很多。令 $f_{i,j}$ 表示箱子到达 $(i,j)$ 时的最小次数，每次转移只需判断目标方向的对面是否是空地即可。

但有了沉重货物的限制，会导致人并不一定能到达箱子旁的空地（即使初始时他可以到达）。

不过不难发现，当人推动一次箱子时，他将会“取代”箱子原本的位置。也就是说，判断人是否能到达空地，实际上是判断箱子上次的位置是否能到达那里。而方向只有四个，令 $f_{i,j,0/1/2/3}$ 表示箱子到达 $(i,j)$ ，且上次它在现在的 上/下/左/右 时的最小次数。每次转移时，从上次的位置出发进行搜索，判断是否能到达目标方向对面的空地即可。

时间复杂度大常数$O(n^4)$，无法通过。

上述算法的瓶颈在于，每次转移时都要进行一次搜索，包含了大量的重复计算。我们希望通过一些预处理优化这一过程。

实际上已经很明显了。我们把每个空地抽象成点，向四周的空地连边。箱子放于 $(x,y)$ 时人无法从 $(a,b)$ 到达 $(c,d)$ ，实际上就是说 $(x,y)$ 是原图的一个割点，将 $(a,b)$ 所在连通块与 $(c,d)$ 所在连通块分离。相反，若 $(a,b)$ 与 $(c,d)$ 在同一连通块中，人肯定能相互到达。这样，通过预处理原图的相关$dcc$信息，我们可以做到$O(1)$的转移。

关于 $f$ 的初始化，需要从人的出发点单独搜一次，记录初始时人能到达的箱子旁的空地。

码量稍大，不过每一部分相对简单。

COGS的这一题是超级满配版本

比洛谷的要强力的多：894. 追查坏牛奶 - COGS

额外要求是：求出最小割流量，同时求出割边最小，同时字典序最小的方案

输出割掉的边

最小割流量好求，最小割边的数量也好求，但同时确定哪条边不太好弄，因为存在方法互斥

首先：最小割流量就是跑最大流的结果

求最小割边的数量，需要在刚刚跑完最大流的网络上

把所有的满流边流量重新标记为1，不满流的重新标记为INF

在新的网络上跑一次最大流

这个时候得到的流量就是最小割边的数量

正确性：

满流边一定是某条流量通路的瓶颈路(虽然不一定是唯一瓶颈路)

把满流的边标记成1去跑增广路

得到的结果就是没有公共边的流量通路的条数(因为公共边只允许通过1点流量被计算一次)

那么就给这这些流量通路每个断开一条边即可(如果存在公共边先断开公共边)

如何求最小字典序的方案：

在最小割的情况下

首先要记住，我们一定是优先断开边权最大的必须满流边(删去这条边后，重新对整个网络跑最大流，最大流量会减小这个边的边权那么多(也就是这条边的传递作用无可替代))

那么找最小字典序方案也出来了：在正常的图上，先跑一次最大流

然后枚举所有边（首先把边按照边权(大到小)-字典序(小到大)两个关键字排序）

先复原整个网络到未增广形态

然后尝试删去这条边，看最大流结果减少的是否是这条边流量那么多

如果是，说明这是关键边，记录这条边会被删除(贪心保证了删除的边数目最少，因为这条边满流，不删它就要删和它在同一支流的多条边) 把这条边永久性删除，并将最大流的结果减小(该边的流量)那么多

这就导致你需要先用正常的边权跑DINIC，再用1和INF的边权跑DINIC，再用正常的边权去找应当被删除的边

#include<bits/stdc++.h>
 
using namespace std;
 
int t;
int a,b,c;
 
int main() {
	freopen("csp2022pj_pow.in","r",stdin);
	freopen("csp2022pj_pow.out","w",stdout);
		cin>>a>>b;
		c=(pow(a,b));
		if(c<0) {
			cout<<-1;
		} else {
			cout<<c;
		}
		cout<<endl;
 
	return 0;

}



//很简单的一道题，用pow函数就行了

更好的阅读体验

补充：这个解法是我自己的，相当麻烦，有比我简洁的 DP 做法，还有 dottle 老师的神奇最短路做法，推荐去洛谷题解看看。

首先，看到 $k\le 3$ 的范围，显然是要分类讨论。

k=1

显然，最小花费即为 $u\to v$ 在树上路径的点权和。倍增预处理，每次查询 LCA 然后树上前缀和即可。

时间复杂度 $\mathcal O((n+m)\log n)$。

k=2

先考虑暴力的做法。将 $u\to v$ 在树上的路径拆下来，将点权写作序列 $b_{1\sim p}$ 研究。

我们用动态规划解决这个问题。设 $f(i)$ 表示 $1\sim i$ 的最小花费。

初始状态：$f(1)=b_1$。

状态转移方程：$f(i)=\min\{f(i-1)+b_i,f(i-2)+b_i\}$。

如果对矩阵很熟悉，不难发现这个就是一个矩阵优化的板子。

不过此处 $b_i$ 是变量，无法进行矩阵快速幂，当时考场上想到这里我脑子莫名其妙宕机了，感觉这题正解绝对是矩阵，但这个东西不会处理啊，然后就彻底蒙了，完全想偏了，最后打了暴力。

实际上和快速幂没有任何关系。因为是树上的静态查询问题，自然可以往倍增想。

因为矩阵满足交换律和结合律，完全可以把矩阵先存起来预处理，最后查询的时候再一次倍增求解。

先把上面那个式子写成矩阵：

$$\begin{bmatrix}f(i-1) & f(i-2)\end{bmatrix}\times\begin{bmatrix}a_i & 0\\a_i & +\infty\end{bmatrix}=\begin{bmatrix}f(i) & f(i-1)\end{bmatrix}$$

为了方便，我们定义 $t=\text{LCA}(u,v)$，$k=3$ 时亦然。

把中间的转移矩阵存起来倍增预处理一下，询问的时候，因为正着走和倒着走没有区别，我们把 $u\to t\to v$ 拆成 $u\to t,v\to t$ 两条链，以 $u\to t$ 为例：

初始向量矩阵：

$$\begin{bmatrix}a_u & +\infty \end{bmatrix}$$

然后把 $fa_u\to t$ 上的转移矩阵全乘起来，就得到了 $u\to t$ 这条链上的答案。

类似地处理 $v\to t$，接下来考虑合并答案。

因为 $k=2$，只有两种可能：$u$ 走到 $t$ 再走到 $v$，或者不经过 $t$，直接从 $t$ 在 $u\to v$ 路径上的两个子节点处穿过。

记 $u\to t$ 的矩阵为 $P$，$v\to t$ 的矩阵为 $Q$，因为可以写作一维向量的形式，为了方便，我们直接将 $P$ 中的元素用类似序列下标的形式表示，即 $P(0),P(1)$。下面 $k=3$ 的情况里我们仍采用这种称呼。

针对两种情况，答案分别为 $P(0)+Q(0)-a_t,P(1)+Q(1)$，两者取 $\text{min}$ 即可。

时空复杂度 $\mathcal O(2^3\times (n+m)\log n)$。

k=3

其实 $k=3$ 大体思路和 $k=2$ 完全一致，只不过有一个小细节：答案路径上的节点不一定都是 $u\to v$ 这条链上的。

原因很简单，比如链上的点权都是 $10^9$ 级别，而与链相连的节点中有一个点权是 1，那走这个点显然更优。

题解里大部分做法是将距离设入状态中，我当时并没有想到，而是直接把链接出去的点再设计一个方程。

还是先考虑一条链上的暴力，因为与 $u$ 相连的点中，只有点权最小的有效，设这个最小点权为 $c_u$。

在 $k=2$ 的情况上再加一条：设 $g(i)$ 表示走到 $i$ 连接的点上的最小路径花费。

状态转移方程：

$$f(i)=\min\{f(i-1)+a_i,f(i-2)+a_i,f(i-3)+a_i,g(i-1)+a_i,g(i-2)+a_i\}\\g(i)=\min\{f(i-1)+c_i,f(i-2)+c_i,g(i-1)+c_i\}$$

考虑将这个东西写成矩阵，那么样子就长这样：

$$\begin{bmatrix}f(i-1) & f(i-2) & f(i-3) & g(i-1) & g(i-2)\end{bmatrix}\times \begin{bmatrix}a_i & 0 & +\infty & b_i & +\infty\\a_i & +\infty & 0 & b_i & +\infty\\a_i & +\infty & +\infty & +\infty & +\infty\\a_i & +\infty & +\infty & b_i & 0\\a_i & +\infty & +\infty & +\infty & +\infty\end{bmatrix}\\=\begin{bmatrix}f(i) & f(i-1) & f(i - 2) & g(i) & g(i-1)\end{bmatrix}$$

倍增预处理和查询就很类似了，略过。

最后的合并情况很多，这里我直接把所有情况对应的式子列出来，因为用文字真的很难写出来 QAQ，理解一下叭 awa，有兴趣可以自己推一下，如果实在嫌我的方法麻烦还是看别的大佬的题解吧 qwq：

$P(0)+Q(0)-a_t$

$P(3)+ Q(3)-c_t$

$P(1)+Q(1)$

$P(1)+Q(2)$

$P(1)+Q(4)$

$P(4)+Q(1)$

$P(2)+Q(1)$

所有情况取 $\text{min}$ 即可。时间复杂度 $\mathcal O(5^3\times (n+m)\log n)$。

zyf 的题解，写得比我好 QAQ

不难发现，答案为 YES，当且仅当所有点的出度均为 1。

考虑如何维护每个点的出度。

暴力的做法是对于每个点维护两个 set，分别表示当前与之相连/不相连的点，暴力删点加点。如果没有 $t=4$，不难发现总操作次数是 $\mathcal O(n+q)$ 级别的，可以获得 60 pts。

（据说这道题可以通过玄学暴力优化在民间数据拿到满分，毕竟这题的数据并不好造，很难有极限数据）

（然而我考场上尝试玄学暴力乱搞，结果全输出 NO，爆零了 QAQ）

upd：现在还没有出数据，但据说全输出 NO 能有 45 pts？乱搞选手赢麻了。

再次 upd：出数据了，我这种乱搞法居然 50pts，赢麻了，但是 rp-- 了 QAQ。

计算了一下，前 60 pts 暴力，后面全输出 NO，能有 80 pts，已经不比正解低多少了。

这道题的核心就是维护出度为 1 的点数，而有了 $t=4$ 的操作会变得非常棘手，没有任何数据结构可以维护。

一般来说（至少以窝之前打的一场 CF 看来），这种情况可以转向随机化。

考虑哈希。对每个点赋一个独一无二的权值（我采用了类似字符串哈希的构造方式），设第 $i$ 个点点权为 $a_i$，定义 $tot=\sum\limits_{i=1}^n a_i,ans=\sum\limits_{i=1}^n deg_i\times a_i$。

其中 $deg_i$ 表示点 $i$ 的出度。

由于点权都是独一无二的，若 $ans=tot$，那么就有极大的概率满足 $\forall i\in [1,n],deg_i=1$。

$tot$ 可以直接计算，而 $ans$ 的维护也相当简单，单次操作时间复杂度 $\mathcal O(1)$。

总时间复杂度为 $\mathcal O(n)$，目前在 InfOJ 上的民间数据这种方法可以拿到满分。

如果还不保险，还可以多取几个模数或点权。

upd：似乎不用我这样写，把求和改成异或，直接随机权值就完全能过了 /kel