首页 > ACM题库 > HDU-杭电 > HDU 3100-Series / Parallel Resistor Circuits[解题报告]HOJ
2014
03-02

HDU 3100-Series / Parallel Resistor Circuits[解题报告]HOJ

Series / Parallel Resistor Circuits

问题描述 :

A series/parallel resistor circuit is shown here.

Defense of the Ancients

The resistance value is given next to each resistor. Connection points (wires connecting two or more resistors together, are denoted by an uppercase letter. A and Z are reserved for the names of the connection points which are the endpoints of the circuit. Our goal is to calculate the equivalent resistance of the circuit (i.e., the equivalent resistance between A and Z).

Within the circuit, a resistor can be specified by a triple consisting of the connection points at either endpoint, and the resistance. The resistor labelled “9" could be specified as either (C, D, 9) or (D, C, 9). A circuit specification is the set of all resistor specifications.

A pair of resistors is in series if one of either of their endpoints have a common connection point that is not use by any other resistor (e.g., the resistors labelled “6" and “9" are both connected to C, which is not connected to anything else). Two series resistors can be replaced by an equivalent single resistor whose resistance is the sum of the replaced resistors (15, in the previous example).

A pair of resistors is in parallel if both their endpoints have common connection points (e.g., the resistors labelled “3" and “10" above are both connected to R and D). Two parallel resistors can be replaced by an equivalent single resistor whose resistance is the inverse of the sum of the inverses of the two resistors ( (1/3 + 1/10)-1 = 2.307692 , in the previous example).

Defense of the Ancients

The equivalent resistance of a well-formed series-parallel resistor circuit can be determined by successively replacing a series or parallel resistor pair by the single equivalent resistor, until only one is left.

Not all circuits can be decomposed into series and parallel components. The Wheatstone Bridge, shown here, is a classic example of a circuit that is not considered a well-formed series-parallel resistor circuit.

Defense of the Ancients

输入:

There will be multiple circuit specifications. The first input line for each circuit specification is an integer N (N < 1000 ), the number of resistors in the circuit. This is followed by N lines, each being a resistor specification in the form: X Y r , where X and Y are uppercase characters, and r is a positive integer resistance (r < 100 ). The equivalent resistance is guaranteed never to be greater than 100.

A circuit with N = 0 indicates the last circuit, and should not be processed.

输出:

There will be multiple circuit specifications. The first input line for each circuit specification is an integer N (N < 1000 ), the number of resistors in the circuit. This is followed by N lines, each being a resistor specification in the form: X Y r , where X and Y are uppercase characters, and r is a positive integer resistance (r < 100 ). The equivalent resistance is guaranteed never to be greater than 100.

A circuit with N = 0 indicates the last circuit, and should not be processed.

样例输入:

8
N R 2
D R 3
R N 2
R D 10
Z R 7
C D 9
N C 6
A N 4
2
A Z 3
Z A 10
2
P A 6
P Z 9
5
A B 1
B Z 4
A C 8
C Z 19
B C 12
0

样例输出:

11.945
2.308
15.000
-1.000

#include <bits/stdc++.h>

using namespace std;

vector<double> adj[26][26];
int deg[26];

int main() {
  int n;
  while (cin >> n, n) {
    char v, w; double r;
    for (int i = 0; i < 26; i++) {
      for (int j = 0; j < 26; j++) {
        adj[i][j].clear();
      }
    }
    
    for (int i = 0; i < n; i++) {
      cin >> v >> w >> r;
      adj[v-'A'][w-'A'].push_back(r);
      adj[w-'A'][v-'A'].push_back(r);
    }
    
    for (int k = 0; k < n; k++) {
      //reducing parallel resistors
      for (int i = 0; i < 26; i++) {
        for (int j = 0; j < 26; j++) {
          if (adj[i][j].size() > 1) {
            double inv_sum = 0;
            for (int s = 0; s < adj[i][j].size(); s++) {
              inv_sum += 1.0/adj[i][j][s];
            }
            adj[i][j].clear(); adj[j][i].clear();
            adj[i][j].push_back(1.0/inv_sum); adj[j][i].push_back(1.0/inv_sum);
          }
        }
      }
      
      memset(deg, 0, sizeof deg);
      for (int i = 0; i < 26; i++) {
        for (int j = 0; j < 26; j++) {
          if (adj[i][j].size()) deg[i]++;
        }
      }
      
      //reducing series resistors
      for (int i = 0; i < 26; i++) {
        for (int j = 0; j < 26; j++) {
          for (int l = 0; l < 26; l++) {
            if (i == l || i == j || j == l) continue;
            if (j == 0 || j == 25) continue;
            if (adj[i][j].size() && adj[j][l].size()) {
              if (deg[j] != 2) break;
              double r = adj[i][j][0] + adj[j][l][0];
              adj[i][j].clear(); adj[j][i].clear();
              adj[j][l].clear(); adj[l][j].clear();
              adj[i][l].push_back(r); adj[l][i].push_back(r);
              deg[j] = 0; deg[i]++; deg[l]++;
            }
          }
        }
      }
    }
    
    bool reduced = true;
    for (int i = 1; i < 25; i++) {
      if (deg[i] != 0) reduced = false;
    }
    
    double ans = 0;
    if (!reduced || adj[0][25].empty()) ans = -1;
    else ans = adj[0][25][0];
    
    cout << fixed << setprecision(3) << ans << endl;
  }
	return 0;
}

  1. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!