USACO 1.4 Mother's Milk

Mother's Milk

Farmer John has three milking buckets of capacity A, B, and C liters. Each of the numbers A, B, and C is an integer from 1 through 20, inclusive. Initially, buckets A and B are empty while bucket C is full of milk. Sometimes, FJ pours milk from one bucket to another until the second bucket is filled or the first bucket is empty. Once begun, a pour must be completed, of course. Being thrifty, no milk may be tossed out.

Write a program to help FJ determine what amounts of milk he can leave in bucket C when he begins with three buckets as above, pours milk among the buckets for a while, and then notes that bucket A is empty.

PROGRAM NAME: milk3

INPUT FORMAT

A single line with the three integers A, B, and C.

SAMPLE INPUT (file milk3.in)

8 9 10

OUTPUT FORMAT

A single line with a sorted list of all the possible amounts of milk that can be in bucket C when bucket A is empty.

SAMPLE OUTPUT (file milk3.out)

1 2 8 9 10

SAMPLE INPUT (file milk3.in)

2 5 10

SAMPLE OUTPUT (file milk3.out)

5 6 7 8 9 10

题目大意：倒牛奶。。。。你有三个筒子ABC会告诉你容积，开始的时候AB都是空的，C是满的，问你在不把牛奶倒出三个筒子之外的情况下，在A桶是空的情况下，C桶有多少奶，顺序输出所有可能性。
思路：没什么说的了，BFS。代码写在下面

  1 /*
  2 ID:fffgrdcc1
  3 PROB:milk3
  4 LANG:C++
  5 */
  6 #include<cstdio>
  7 #include<iostream>
  8 #include<algorithm>
  9 using namespace std;
 10 bool bo[21][21][21]={0};
 11 struct str
 12 {
 13     int a,b,c;
 14 }e[10000];
 15 int cnt=1;
 16 int q[10000],tail,head;
 17 int a,b,c,A,B,C;
 18 int main()
 19 {
 20     freopen("milk3.in","r",stdin);
 21     freopen("milk3.out","w",stdout);
 22     scanf("%d%d%d",&A,&B,&C);
 23     head=-1;tail=0;e[0].a=e[0].b=0;e[0].c=C;q[0]=0;bo[0][0][C]=1;
 24     while(head<tail)
 25     {
 26         head++;
 27         int temp;
 28         a=e[head].a,b=e[head].b,c=e[head].c;
 29         temp=min(a,C-c);//a2c
 30         a-=temp;c+=temp;
 31         if(!bo[a][b][c])
 32         {
 33             bo[a][b][c]=1;
 34             q[++tail]=cnt;
 35             e[++cnt].a=a;
 36             e[cnt].b=b;
 37             e[cnt].c=c;
 38         }
 39         a+=temp;c-=temp;
 40 
 41         temp=min(A-a,c);//c2a
 42         a+=temp;c-=temp;
 43         if(!bo[a][b][c])
 44         {
 45             bo[a][b][c]=1;
 46             q[++tail]=cnt;
 47             e[++cnt].a=a;
 48             e[cnt].b=b;
 49             e[cnt].c=c;
 50         }
 51         a-=temp;c+=temp;
 52 
 53         temp=min(a,B-b);//a2b
 54         a-=temp;b+=temp;
 55         if(!bo[a][b][c])
 56         {
 57             bo[a][b][c]=1;
 58             q[++tail]=cnt;
 59             e[++cnt].a=a;
 60             e[cnt].b=b;
 61             e[cnt].c=c;
 62         }
 63         a+=temp;b-=temp;
 64 
 65         temp=min(A-a,b);//b2a
 66         a+=temp;b-=temp;
 67         if(!bo[a][b][c])
 68         {
 69             bo[a][b][c]=1;
 70             q[++tail]=cnt;
 71             e[++cnt].a=a;
 72             e[cnt].b=b;
 73             e[cnt].c=c;
 74         }
 75         a-=temp;b+=temp;
 76 
 77         temp=min(b,C-c);//b2c
 78         b-=temp;c+=temp;
 79         if(!bo[a][b][c])
 80         {
 81             bo[a][b][c]=1;
 82             q[++tail]=cnt;
 83             e[++cnt].a=a;
 84             e[cnt].b=b;
 85             e[cnt].c=c;
 86         }
 87         b+=temp;c-=temp;
 88 
 89         temp=min(c,B-b);//c2b
 90         c-=temp;b+=temp;
 91         if(!bo[a][b][c])
 92         {
 93             bo[a][b][c]=1;
 94             q[++tail]=cnt;
 95             e[++cnt].a=a;
 96             e[cnt].b=b;
 97             e[cnt].c=c;
 98         }
 99         b-=temp;c+=temp;
100     }
101     int firflag=1;
102     for(int i=0;i<=C;i++)
103     {
104         b=C-i;
105         if(bo[0][b][i])
106             if(firflag)
107                 printf("%d",i),firflag=0;
108             else printf(" %d",i);
109     }
110     printf("
");
111     return 0;
112 }

View Code

对了，输出格式很重要，提交前别忘记检查，血与泪的教训