每种状态下,只有六种移动的情况:A->B, A->C, B->A, B->C, C->A, C->B, 一一判断,BFS,直到没有新的状态出现。
/* ID: bbsunch2 PROG: milk3 LANG: C++ */ #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<vector> #include<queue> #include<map> #include<set> #include<cmath> #include<algorithm> #include<fstream> using namespace std; vector<int> aStates; vector<int> bStates; vector<int> cStates; vector<int> cValues; int aCapacity, bCapacity, cCapacity; bool newState = false; bool check_exist(const int a, const int b, const int c){ for(int i = 0; i < aStates.size(); i++){ if((a == aStates[i]) && (b == bStates[i]) && (c == cStates[i])){ //fout << a << " " << aStates[i] << " " << b << " " << bStates[i] << " " << c << " " << cStates[i] << endl; return true; } } return false; } int insert_states(const int as, const int bs, const int cs){ //fout << aStates.size() << ": " << as << " " << bs << " " << cs << endl; aStates.push_back(as); bStates.push_back(bs); cStates.push_back(cs); if (as == 0){ //cout << cs << endl; cValues.push_back(cs); } newState = true; } int main(){ ofstream fout("milk3.out"); ifstream fin("milk3.in"); fin >> aCapacity; fin >> bCapacity; fin >> cCapacity; //cout << cCapacity << endl; //initialize insert_states(0,0,cCapacity); //endStates.push_back(false); int currentStartIndex = 0; int currentEndIndex = aStates.size() - 1; // record current phase's states, so this is basically a bfs while(1){ // iterate phases for(int i = currentStartIndex; i <= currentEndIndex; i++){ //fout << "considering " << i << endl; // for each state in current phase, we have six operations to do, we use if if(aStates[i] > 0 && (cStates[i] < cCapacity)){ //fout << "A->C" << endl; int transValue = min(cCapacity-cStates[i], aStates[i]); int as = aStates[i] - transValue; int cs = cStates[i] + transValue; int bs = bStates[i]; if(!check_exist(as, bs, cs)){ insert_states(as,bs,cs); } } if(aStates[i] > 0 && (bStates[i] < cCapacity)){ //fout << "A->B" << endl; int transValue = min(bCapacity-bStates[i], aStates[i]); int as = aStates[i] - transValue; int bs = bStates[i] + transValue; int cs = cStates[i]; if(!check_exist(as, bs, cs)){ insert_states(as,bs,cs); } } if(bStates[i] > 0 && (cStates[i] < cCapacity)){ //fout << "B->C" << endl; int transValue = min(cCapacity-cStates[i], bStates[i]); int bs = bStates[i] - transValue; int cs = cStates[i] + transValue; int as = aStates[i]; if(!check_exist(as, bs, cs)){ insert_states(as,bs,cs); } } if(bStates[i] > 0 && (aStates[i] < aCapacity)){ //fout << "B->A" << endl; int transValue = min(aCapacity-aStates[i], bStates[i]); int bs = bStates[i] - transValue; int as = aStates[i] + transValue; int cs = cStates[i]; if(!check_exist(as, bs, cs)){ insert_states(as,bs,cs); } } if(cStates[i] > 0 && (aStates[i] < aCapacity)){ //fout << "C->A" << endl; int transValue = min(aCapacity-aStates[i], cStates[i]); int cs = cStates[i] - transValue; int as = aStates[i] + transValue; int bs = bStates[i]; if(!check_exist(as, bs, cs)){ insert_states(as,bs,cs); } } if(cStates[i] > 0 && (bStates[i] < bCapacity)){ //fout << "C->B" << endl; int transValue = min(bCapacity-bStates[i], cStates[i]); int cs = cStates[i] - transValue; int bs = bStates[i] + transValue; int as = aStates[i]; if(!check_exist(as, bs, cs)){ insert_states(as,bs,cs); } } } currentStartIndex = currentEndIndex + 1; currentEndIndex = aStates.size() - 1; if(!newState) break; newState = false; } sort(cValues.begin(), cValues.end()); int previousC = -1; for(int i = 0; i < cValues.size(); i++){ if(cValues[i] != previousC){ if(i != cValues.size()-1){ cout << cValues[i] << " "; fout << cValues[i] << " "; }else{ cout << cValues[i] << endl; fout << cValues[i] << endl; } previousC = cValues[i]; } } fout.close(); return 0; }
相关推荐
USACO题解+代码+翻译,好东西,超级齐全,对大家帮助不小,特别是现在nocow挂了
usaco第五章milk4的解题代码,供算法初学者参考
USACO题解(NOCOW整理版).doc
我的USACO题解和程序
USACO题解及中文译题1.1.1-2.4.5 题目为TXT格式文档,代码为C++语言所编写
USACO所有题目的题解 NOCOW整理版
里面有usaco前几节的程序和代码,欢迎使用,希望对你有所帮主。
Usaco总结&题解 一位大牛写的Usaco的总结,并有所有题的题解,推荐!!
数据结构机考所参考的USACO网站所有题目的解题思路,资源比较稀有!
个人usaco题解,更新至4.2
USACO教程,包含USACO全部英文原题,题解(NOCOW整理版),翻译,教程,代码,测试数据。
usaco全部题解。 网址:blog.csdn.net/jiangshibiao
其中包含了USACO前些年的月赛试题和部分试题的数据,部分试题的详细题解,英文原题目与翻译后的题目,与题解一一对应
usaco的某道题的题解
非常详细的题解,比较全的,个人觉得刷题者可以入手,帮助非常大。
USACO月赛题解1
USACO(即美国高中生的编程竞赛网站)中的 pprime 题的题解
丰富的USACO1.1--2.3.4的所有题解
milk3 的答案,有注释哦!!!!!!里面有详细的求解过程哦