首页 > 代码库 > 【USACO 1.4.4】母亲的牛奶

【USACO 1.4.4】母亲的牛奶

2024-07-08 05:01:08   213人阅读

【题目描述】

 农民约翰有三个容量分别是A,B,C升的桶，A,B,C分别是三个从1到20的整数，
最初，A和B桶都是空的，而C桶是装满牛奶的。有时，约翰把牛奶从一个桶倒到另一个桶中，直到被灌桶装满或原桶空了。当然每一次灌注都是完全的。由于节约，牛奶不会有丢失。
写一个程序去帮助约翰找出当A桶是空的时候，C桶中牛奶所剩量的所有可能性。

【格式】

INPUT FORMAT:
(file milk3.in)
单独的一行包括三个整数A,B和C。
OUTPUT FORMAT:
(file milk3.out)
只有一行，升序地列出当A桶是空的时候，C桶牛奶所剩量的所有可能性。

【分析】

直接上BFS就行了，注意判重。

 1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <cstring> 5 #include <algorithm> 6 #include <queue> 7 const int Max=10000; 8 #define hash(t) h[t.a][t.b][t.c] 9 using namespace std;10 struct State{int a,b,c;}data;11 bool h[21][21][21],h_2[21];//哈希表 12 int A,B,C,point=0,ans[Max];13 void bfs();14 void check(State t);15 int main()16 {17     //文件操作 18     freopen("milk3.in","r",stdin);19     freopen("milk3.out","w",stdout);20     scanf("%d%d%d",&A,&B,&C);21     data.a=data.b=0;data.c=C;//初始状态22     bfs(); 23     sort(ans,ans+point);24     for (int i=0;i<point;i++) printf("%d ",ans[i]);25     return 0;26 }27 void bfs()28 {29      memset(h,0,sizeof(h));//初始化哈希表30      memset(h_2,0,sizeof(h_2)); 31      queue<State>Q;32      Q.push(data);33      hash(data)=1;34      check(data);35      while (!Q.empty())36      {37            State u=Q.front(),v;Q.pop();38            v=u;39            //倒满的 40            if (v.a>=B-v.b) {v.a-=B-v.b;v.b=B;if (hash(v)==0) {Q.push(v);hash(v)=1;check(v);}}v=u;41            if (v.b>=A-v.a) {v.b-=A-v.a;v.a=A;if (hash(v)==0) {Q.push(v);hash(v)=1;check(v);}}v=u;42            if (v.a>=C-v.c) {v.a-=C-v.c;v.c=C;if (hash(v)==0) {Q.push(v);hash(v)=1;check(v);}}v=u;43            if (v.c>=A-v.a) {v.c-=A-v.a;v.a=A;if (hash(v)==0) {Q.push(v);hash(v)=1;check(v);}}v=u;44            if (v.c>=B-v.b) {v.c-=B-v.b;v.b=B;if (hash(v)==0) {Q.push(v);hash(v)=1;check(v);}}v=u;45            if (v.b>=C-v.c) {v.b-=C-v.c;v.c=C;if (hash(v)==0) {Q.push(v);hash(v)=1;check(v);}}v=u;46            //倒不满 47            if (v.a<B-v.b) {v.b+=v.a;v.a=0;if (hash(v)==0) {Q.push(v);hash(v)=1;check(v);}}v=u;48            if (v.b<A-v.a) {v.a+=v.b;v.b=0;if (hash(v)==0) {Q.push(v);hash(v)=1;check(v);}}v=u;49            if (v.a<C-v.c) {v.c+=v.a;v.a=0;if (hash(v)==0) {Q.push(v);hash(v)=1;check(v);}}v=u;50            if (v.c<A-v.a) {v.a+=v.c;v.c=0;if (hash(v)==0) {Q.push(v);hash(v)=1;check(v);}}v=u;51            if (v.c<B-v.b) {v.b+=v.c;v.c=0;if (hash(v)==0) {Q.push(v);hash(v)=1;check(v);}}v=u;52            if (v.b<C-v.c) {v.c+=v.b;v.b=0;if (hash(v)==0) {Q.push(v);hash(v)=1;check(v);}}v=u;53      }54 }55 void check(State t)56 {57      if (t.a==0 && h_2[t.c]==0)58      {59          ans[point++]=t.c;60          h_2[t.c]=1; 61      }62      return;63 }

 


联系
我们