USACO Section 1.4 Mother's Milk

/*
ID: lucien23
PROG: milk3
LANG: C++
*/

#include<iostream>
#include<fstream>
#include<set>
#include<string>
using namespace std;

typedef struct
{
	int a;
	int b;
	int c;
}BucketVals;

struct comp
{
	bool operator()(const BucketVals &bucketVal1,const BucketVals &bucketVal2) const
	{
		string str1="",str2="";
		str1+=bucketVal1.a+‘0‘;
		str1+=bucketVal1.b+‘0‘;
		str1+=bucketVal1.c+‘0‘;
		str2+=bucketVal2.a+‘0‘;
		str2+=bucketVal2.b+‘0‘;
		str2+=bucketVal2.c+‘0‘;
		return str1<str2;
	}
};

void pour(BucketVals nowVal,BucketVals totalVal,bool isFirst);
set<int> cVals;
set<BucketVals,comp> bucketVals;
int main()
{
	ifstream infile("milk3.in");
	ofstream outfile("milk3.out");
	if(!infile || !outfile)
	{
		cout<<"file operation failure!"<<endl;
		return -1;
	}

	int A,B,C;
	infile>>A>>B>>C;
	BucketVals nowVal,totalVal;
	totalVal.a=A;
	totalVal.b=B;
	totalVal.c=C;
	nowVal.a=0;
	nowVal.b=0;
	nowVal.c=C;
	pour(nowVal,totalVal,true);
	set<int>::iterator it=cVals.begin();
	while(it!=cVals.end())
	{
		outfile<<*it;
		it++;
		if(it!=cVals.end())
			outfile<<" ";
	}
	outfile<<endl;
	return 0;
}

void pour(BucketVals nowVal,BucketVals totalVal,bool isFirst)
{
	if(!isFirst && nowVal.a==0 && nowVal.b==0 && nowVal.c==totalVal.c || bucketVals.find(nowVal)!=bucketVals.end())
		return;
	bucketVals.insert(nowVal);
	if(nowVal.a==0)
		cVals.insert(nowVal.c);
	int exVal;
	BucketVals newVals;
	if(nowVal.a>0)//A桶中有牛奶
	{
		//A-->B
		exVal=min(nowVal.a,totalVal.b-nowVal.b);
		newVals.a=nowVal.a-exVal;
		newVals.b=nowVal.b+exVal;
		newVals.c=nowVal.c;
		pour(newVals,totalVal,false);

		//A-->C
		exVal=min(nowVal.a,totalVal.c-nowVal.c);
		newVals.a=nowVal.a-exVal;
		newVals.c=nowVal.c+exVal;
		newVals.b=nowVal.b;
		pour(newVals,totalVal,false);
	}

	if(nowVal.b>0)//B桶中有牛奶
	{
		//B-->A
		exVal=min(nowVal.b,totalVal.a-nowVal.a);
		newVals.a=nowVal.a+exVal;
		newVals.b=nowVal.b-exVal;
		newVals.c=nowVal.c;
		pour(newVals,totalVal,false);

		//B-->C
		exVal=min(nowVal.b,totalVal.c-nowVal.c);
		newVals.b=nowVal.b-exVal;
		newVals.c=nowVal.c+exVal;
		newVals.a=nowVal.a;
		pour(newVals,totalVal,false);
	}

	if(nowVal.c>0)//C桶中有牛奶
	{
		//C-->A
		exVal=min(nowVal.c,totalVal.a-nowVal.a);
		newVals.a=nowVal.a+exVal;
		newVals.c=nowVal.c-exVal;
		newVals.b=nowVal.b;
		pour(newVals,totalVal,false);

		//C-->B
		exVal=min(nowVal.c,totalVal.b-nowVal.b);
		newVals.b=nowVal.b+exVal;
		newVals.c=nowVal.c-exVal;
		newVals.a=nowVal.a;
		pour(newVals,totalVal,false);
	}
}

USACO Section 1.4 Mother's Milk

原文：http://blog.csdn.net/lucienduan/article/details/19505345