#include #include #include #include #include #include #include using namespace std; /*Resistors connected to each point. First = the point on the other end of the resistor, second = the resistance value.*/ vector > resistors(26); //Number of neighbors each point has. int numNeighbors[26]; /* Inserts a resistor connecting points "begin" and "end" with resistance "value". If a resistor already exists there, inserts the new resistor in parallel. */ void putRes(int begin, int end, double value) { if (resistors[begin][end] > 0) //A resistor already exists, insert in parallel { resistors[begin][end] = 1.0/(1.0/resistors[begin][end] + 1.0/value); } else //This is the only resistor between the 2 points { resistors[begin][end] = value; numNeighbors[begin]++; } } int main() { ifstream infile("circuits.judge"); ofstream outfile("circuits.out"); int circuitNum = 0; while(true) { circuitNum++; //Reset the data structures for (int i = 0; i < 26; i++) { numNeighbors[i] = 0; resistors[i].clear(); } int numResistors; infile >> numResistors; if (numResistors == 0) break; for (int i = 0; i < numResistors; i++) { char ch1, ch2; double value; infile >> ch1 >> ch2 >> value; int point1 = ch1 - 'A'; //Convert characters to integers for easy storage int point2 = ch2 - 'A'; putRes(point1, point2, value); //Keep track of the resistor in both directions putRes(point2, point1, value); } bool reduced = false; //Has anything been reduced on this loop iteration? do { reduced = false; for (int i = 1; i < 25; i++) //B through Y - don't want to eliminate A or Z { //The point is only connected to 2 resistors, so they can be combined in series. if (numNeighbors[i] == 2) { reduced = true; int begin = (resistors[i].begin())->first; //one of the point's neighbors int end = (resistors[i].rbegin())->first; //the other neighbor //Add the new, combined resistor between the 2 neighbors. double newRes = resistors[begin][i] + resistors[i][end]; putRes(begin, end, newRes); putRes(end, begin, newRes); //This point has been reduced away and no longer exists resistors[i].clear(); numNeighbors[i] = 0; //Get rid of this point on its neighbors' neighbor lists. resistors[begin].erase(i); resistors[end].erase(i); numNeighbors[begin]--; numNeighbors[end]--; } } } while (reduced); /* Count the number of resistors left. The count will be 2 * the actual number because each resistor was stored twice.*/ int total = 0; for (int i = 0; i < 26; i++) { total += numNeighbors[i]; } if (total > 2 || //we weren't able to fully reduce the circuit resistors[0].find(25) == resistors[0].end()) //points A and Z are not connected outfile << "Circuit " << circuitNum << ": -1.000" << endl; else { double finalRes = resistors[0][25]; outfile << setprecision(3) << fixed; outfile << "Circuit " << circuitNum << ": " << finalRes << endl; } } return 0; }