今日总结2024/3/22

今日复习了BFS的抽象用法，可以根据实际问题不断枚举所有可能

Acwing 1355.母亲的牛奶

农夫约翰有三个容量分别为 A,B,C升的挤奶桶。

最开始桶 A 和桶 B都是空的，而桶 C里装满了牛奶。

有时，约翰会将牛奶从一个桶倒到另一个桶中，直到被倒入牛奶的桶满了或者倒出牛奶的桶空了为止。

这一过程中间不能有任何停顿，并且不会有任何牛奶的浪费。

请你编写一个程序判断，当 A 桶是空的时候，C 桶中可能包含多少升牛奶，找出所有的可能情况。

输入格式

共一行，包含三个整数 A,B,C。

输出格式

共一行，包含若干个整数，表示 C 桶中牛奶存量的所有可能情况，请将这些数字按升序排列。

数据范围

1≤A,B,C≤20

输入样例1：
8 9 10
输出样例1：
1 2 8 9 10
输入样例2：
2 5 10
输出样例2：
5 6 7 8 9 10

本体枚举所有可能要21*21*21大概8e3,使用结构体来存每种状态中三种桶中牛奶的总量每次进行一次操作将桶里的牛奶进行一次操作并将所有一次操作产生的结果6种加入队列中，此时需要一个数组来记录三个桶的状态是否在之前出现过，当所有桶的状态被记录时，循环就会退出

本体相当于一个结点有六条边链接到另外六个点(六种)的情况，可以用bfs对每次向外扩散(倒一次牛奶的状态)进行记录

#include <iostream>
#include <queue>
using namespace std;
const int N=1e4;
struct node{
    int a,b,c;
}bk[N];
typedef struct node bucket;
bool sum[21][21][21];//所有种类
int con[3];//存每个桶的容量

void bfs(){
    queue<bucket> q;
    bucket st={0,0,con[2]};//起始c是满的
    q.push(st);
    while(!q.empty()){
        bucket tem=q.front();
        sum[tem.a][tem.b][tem.c]=true;
        q.pop();
        for(int i=0;i<3;i++)
        for(int j=0;j<3;j++){//i桶往j桶里倒
            if(i!=j){
                int w[3]={tem.a,tem.b,tem.c};//当前取出的三桶牛奶的存量
                int r=min(w[i],con[j]-w[j]);//算出能倒的值
                //w[i]就是当前要倒的桶内牛奶的存量，con[j]-w[j]就是j桶能接受的量
                //取一个最小值就是符合条件能倒入的量
                w[i]-=r;
                w[j]+=r;//倒进去
                bucket cur;//存倒完的桶
                cur.a=w[0],cur.b=w[1],cur.c=w[2];
                if(!sum[cur.a][cur.b][cur.c]){
                    sum[cur.a][cur.b][cur.c]=true;
                    q.push(cur);
                }
            }
        }
        
    }
}

int main(){
    cin>>con[0]>>con[1]>>con[2];
    bfs();
    
    for(int i=0;i<=con[2];i++)
    for(int j=0;j<=con[1];j++)//枚举c,b桶内的容量
    if(sum[0][j][i]){
        cout<<i<<' ';
        break;//c桶内容量相同的只输出一次
    }
    return 0;
}