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。代码写在下面

 /*

 ID:fffgrdcc1

 PROB:milk3

 LANG:C++

 */

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 bool bo[][][]={};

 struct str

 {

     int a,b,c;

 }e[];

 int cnt=;

 int q[],tail,head;

 int a,b,c,A,B,C;

 int main()

 {

     freopen("milk3.in","r",stdin);

     freopen("milk3.out","w",stdout);

     scanf("%d%d%d",&A,&B,&C);

     head=-;tail=;e[].a=e[].b=;e[].c=C;q[]=;bo[][][C]=;

     while(head<tail)

     {

         head++;

         int temp;

         a=e[head].a,b=e[head].b,c=e[head].c;

         temp=min(a,C-c);//a2c

         a-=temp;c+=temp;

         if(!bo[a][b][c])

         {

             bo[a][b][c]=;

             q[++tail]=cnt;

             e[++cnt].a=a;

             e[cnt].b=b;

             e[cnt].c=c;

         }

         a+=temp;c-=temp;

         temp=min(A-a,c);//c2a

         a+=temp;c-=temp;

         if(!bo[a][b][c])

         {

             bo[a][b][c]=;

             q[++tail]=cnt;

             e[++cnt].a=a;

             e[cnt].b=b;

             e[cnt].c=c;

         }

         a-=temp;c+=temp;

         temp=min(a,B-b);//a2b

         a-=temp;b+=temp;

         if(!bo[a][b][c])

         {

             bo[a][b][c]=;

             q[++tail]=cnt;

             e[++cnt].a=a;

             e[cnt].b=b;

             e[cnt].c=c;

         }

         a+=temp;b-=temp;

         temp=min(A-a,b);//b2a

         a+=temp;b-=temp;

         if(!bo[a][b][c])

         {

             bo[a][b][c]=;

             q[++tail]=cnt;

             e[++cnt].a=a;

             e[cnt].b=b;

             e[cnt].c=c;

         }

         a-=temp;b+=temp;

         temp=min(b,C-c);//b2c

         b-=temp;c+=temp;

         if(!bo[a][b][c])

         {

             bo[a][b][c]=;

             q[++tail]=cnt;

             e[++cnt].a=a;

             e[cnt].b=b;

             e[cnt].c=c;

         }

         b+=temp;c-=temp;

         temp=min(c,B-b);//c2b

         c-=temp;b+=temp;

         if(!bo[a][b][c])

         {

             bo[a][b][c]=;

             q[++tail]=cnt;

             e[++cnt].a=a;

             e[cnt].b=b;

             e[cnt].c=c;

         }

         b-=temp;c+=temp;

     }

     int firflag=;

     for(int i=;i<=C;i++)

     {

         b=C-i;

         if(bo[][b][i])

             if(firflag)

                 printf("%d",i),firflag=;

             else printf(" %d",i);

     }

     printf("\n");

     return ;

 }

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

巴特西

USACO 1.4 Mother's Milk

PROGRAM NAME: milk3

INPUT FORMAT

SAMPLE INPUT (file milk3.in)

OUTPUT FORMAT

SAMPLE OUTPUT (file milk3.out)

SAMPLE INPUT (file milk3.in)

SAMPLE OUTPUT (file milk3.out)

最新文章

热门文章