USACO Mother's Milk(milk3)题解

每种状态下，只有六种移动的情况：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;
}