题解 P3139 【[USACO16FEB]牛奶桶Milk Pails】

一看到此题就联想到了以前用广搜做的一道类似的题...... 广搜做很简单，我还提心吊胆的加了优化，防止TLE 附上评测结果 用时: 0ms / 内存: 3246KB的代码： ```cpp #include <bits/stdc++.h> using namespace std; int b1,b2,need,ans = INT_MAX,kk; struct Node{int x,y,cnt;}; //x为1桶的单位数，y为2桶的单位数 void bfs() { bool vis[101][101][101] = {};memset(vis,0,sizeof(vis));//状态记录数组 queue<Node> q;//防止MLE q.push({0,0,0});vis[0][0][0] = 1; while (!q.empty()) { Node n = q.front();q.pop(); if(n.cnt == kk || n.x == 0 || n.y == 0)//判断 如两个桶里有任意一个为0，也做一次检查（之后可以一直倒空这个桶） { ans = min(ans,abs(n.x + n.y - need));//cout << n.x + n.y << endl; if (n.cnt == kk) continue;//防止不必要状态扩展 } int x = n.x,y = n.y,cnt = n.cnt + 1;//扩展 if(!vis[b1][y][cnt]) q.push({b1,y,cnt}); vis[b1][y][cnt] = 1; if(!vis[x][b2][cnt]) q.push({x,b2,cnt}); vis[x][b2][cnt] = 1; if(!vis[0][y][cnt]) q.push({0,y,cnt}); vis[0][y][cnt] = 1; if(!vis[x][0][cnt]) q.push({x,0,cnt}); vis[x][0][cnt] = 1; int Y = x + y,X = 0; if(Y > b2) X = Y - b2,Y = b2; if(!vis[X][Y][cnt]) q.push({X,Y,cnt}); vis[X][Y][cnt] = 1; X = x + y,Y = 0; if(X > b1) Y = X - b1,X = b1; if(!vis[X][Y][cnt]) q.push({X,Y,cnt}); vis[X][Y][cnt] = 1; } printf("%d",ans); } int main () { scanf("%d%d%d%d",&b1,&b2,&kk,&need); bfs(); return 0; } ```