题解：P3139 [USACO16FEB]Milk Pails S

题外话：他有三个桶 是不是应该改成 两个桶 啊 emmm。

方法： 用 $\texttt{BFS}$ 进行搜索枚举。把三个操作分别转成数学语言即可。

接下来为了表示统一，把当前的两个桶中的牛奶设为 $(m,n)$，则应有 $0 \le m \le X,0 \le n \le Y$。

操作①：装满牛奶。很简单，只要把 $m = X$ 或 $n = Y$ 即可。两种情况分别变为 $(X,n)$ 与 $(m,Y)$。
操作②：倒空牛奶。也十分容易，把 $m = 0$ 或 $n = 0$，对应的两种情况分别变为 $(0,n)$ 与 $(m,0)$。
操作③：相互倒牛奶。这里涉及到多种的分类讨论。首先是第一个桶中的牛奶到给第二个桶中，则会出现两种情况：第一个桶倒完与未倒完(未到完即对应第二个桶已倒满)，将两种情况整理可合并成一个式子：$(m - \min (m,Y - n),\min (Y,n + m))$。第二大类与第一类相反，所以式子改变一下变成：$(\min (X,n + m),n - \min (n,X - m))$。

那么是否需要每一次操作后都将这 $8$ 大类加入到队列中去呢？肯定不需要，否则冗余的操作会使程序 $\texttt{TLE}$。看下 $X,Y$ 的数据范围，$1 \le X,Y \le 100$，开个二维数组 vis[105][105]，vis[i][j] 表示两个桶分别装 $i$ 与 $j$ 的单位的牛奶的情况是否已经出现过。因此我们只需要将未出现过的情况加入到队列中去就行了。

最后就是答案的更新了，不用说，每次在取出当前队列的队首元素后进行判断更新 $ans = \min(ans,M - |m + n|)$ 就完事了啊！

具体实现的代码：

#include <iostream>
#include <queue>
#include <cmath> 
#define INF 0x3f3f3f3f
using namespace std; 
const int MAX = 105;
struct _pair
{
    int dx,dy;
};
bool vis[MAX][MAX];
int x,y,k,m,ans = INF;
queue <_pair> q;  
void search (int num);
int main ()
{
    cin>>x>>y>>k>>m;
    q.push ({0,0});vis[0][0] = 1;//一开始的情况 
    search (0);
    cout<<ans<<endl;
    return 0;
}
void search (int num)
{
    queue <_pair> milk;//将最新的情况压入队列 
    if (num == k + 1) return ;//次数已到,注意是k + 1 次 
    while (!q.empty ())//更新所有可能的情况 
    {
        _pair now = q.front ();q.pop ();
        ans = min (ans,abs (m - now.dx - now.dy));//更新最优答案 |m - m'|
        //若此情况没有出现过，则加入队列中
        
        //装满 
        if (!vis[x][now.dy]) milk.push ({x,now.dy}),vis[x][now.dy] = 1;
        if (!vis[now.dx][y]) milk.push ({now.dx,y}),vis[now.dx][y] = 1;
        
        //倒空
        if (!vis[now.dx][0]) milk.push ({now.dx,0}),vis[now.dx][0] = 1;
        if (!vis[0][now.dy]) milk.push ({0,now.dy}),vis[0][now.dy] = 1; 
        
        //互相倒
        if (!vis[now.dx - min (now.dx,y - now.dy)][min (y,now.dy + now.dx)])
            milk.push ({now.dx - min (now.dx,y - now.dy),min (y,now.dy + now.dx)}),vis[now.dx - min (now.dx,y - now.dy)][min (y,now.dy + now.dx)] = 1;
        if (!vis[min (x,now.dx + now.dy)][now.dy - min (now.dy,x - now.dx)])
            milk.push ({min (x,now.dx + now.dy),now.dy - min (now.dy,x - now.dx)}),vis[min (x,now.dx + now.dy)][now.dy - min (now.dy,x - now.dx)] = 1;
    }
    while (!milk.empty ()) q.push (milk.front ()),milk.pop ();//将所有可能放入 q 中
    search (num + 1); 
}

$\texttt{end:}$ 注意一下递归的边界！！！
if (num == k + 1) return ; 写成 if (num == k) return ; 调了我好久啊 $\texttt{qwq}$！