解題區/解題區 - UVa

UVa 345 - It's Ir-Resist-Able

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. Solution

Problem

A common component in electronic circuits is the resistor. Each resistor has two terminals, and when current flows through a resistor, some of it is converted to heat, thus ``resisting”; the flow of the current. The extent to which it does this is indicated by a single positive numeric value, cleverly called the resistance of the resistor. By the way, the units of resistance are Ohms. Here’s what a single resistor looks like in a diagram of an electronic circuit:

When two resistors are connected in series, as shown below, then their equivalent resistance is just the sum of the resistances of the individual resistors. For example, if the two resistors below had resistances of 100 and 200 Ohms, respectively, then the combined resistance (from point A to point B) would be 300 Ohms. Of course, combining three or more resistors in series would yield a resistance equal to sum of all the individual resistances.

Resistors may also be connected in parallel, like this:

If these two resistors had resistances of 100 and 150 Ohms, then the parallel combination would yield an equivalent resistance between points A and B of

displaymath61

Connecting three resistors in parallel uses the same rule, so a 100 Ohm, 150 Ohm, and 300 Ohm resistor in parallel would yield a combined resistance of just 50 Ohms: that is,

displaymath63

In this problem you’re provided one or more descriptions of resistors and their interconnections. Each possible interconnection point (the terminals of a resistor) is identified by a unique positive integer, its label. And each resistor is specified by giving its two interconnection point labels and its resistance (as a real number).

For example, the input

1 2 100

would tell us that a 100 Ohm resistor was connected between points 1 and 2. A pair of resistors connected in series might be specified like this:

1 2 100
2 3 200

Here we’ve got our 100 Ohm resistor connected at points 1 and 2, and another 200 Ohm resistor connected to points 2 and 3. Two resistors in parallel would be similarly specified:

1 2 100
1 2 150

Once you know how the resistors are interconnected, and the resistance of each resistor, it’s possible to determine the equivalent resistance between any two points using the simple rules given above. In some cases, that is. Some interconnections of resistors can’t be solved using this approach: you won’t encounter any of these in this problem, however.

Notes

  • Be aware that there may be input test cases with some resistors that don’t contribute to the overall resistance between the indicated points. For example, in the last case shown in the Sample Input section below, the resistor between points 1 and 2 is unused. There must be some flow through a resistor if it is to contribute to the overall resistance.
  • No resistor will have its ends connected together. That is, the labels associated with the ends of a resistor will always be distinct.

Input

There will be one or more cases to consider. Each will begin with a line containing three integers N, A, and B. A and B indicate the labels of points between which you are to determine the equivalent resistance. N is the number of individual resistors, and will be no larger than 30. N, A and B will all be zero in the line following the last case. Following each N A B line will be N lines, each specifying the labels of the points where a resistor is connected, and the resistance of that resistor, given as a real number.

Output

For each input case, display a line that includes the case number (they are numbered sequentially starting with 1) and the equivalent resistance, accurate to two decimal places.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
2 1 3
1 2 100
2 3 200
2 1 2
1 2 100
1 2 150
6 1 6
1 2 500
1 3 15
3 4 40
3 5 100
4 6 60
5 6 50
0 0 0

Sample Output

1
2
3
Case 1: 300.00 Ohms
Case 2: 60.00 Ohms
Case 3: 75.00 Ohms

Solution

題目描述：

給定指定的兩個端點 A B，接著會有 N 個電阻，每個電阻值位於端點 X Y 之間。
求 A B 之間的等效電阻，特別注意到端點編號是任意整數，並且有可能兩個端點相同 (A = B)，也有可能會有無會流經的電路區域。

題目解法：

我們假設每個端點的電動勢 (Volt)，使用克希荷夫電路定律（Kirchhoff Circuit Laws）中的 電流定律 ，得到下列公式。

對於每一個端點而言，入電流總量等於出電流總量：

$\sum_{j = 1}^{n} \frac{V_{j} - V_{i}}{R_{i, j}} = 0$

但是題目給定的起點和終點並不會在其中，因此假設起點 V[A] = INF，終點 V[B] = 0，接著算出其他所有點的電動勢。共有 n - 2 條方程式，n - 2 個變數，使用高斯消去求解。

  • 必須預處理與起點、終點之間的電流關係。
  • 特別注意到起點和終點相同，直接輸出等效電阻 0。
  • 端點編號離散化集中處理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <stdio.h> 
#include <string.h>
#include <algorithm>
#include <vector>
#include <math.h>
#include <map>
#include <iostream>
using namespace std;
// learn: http://blog.csdn.net/jiangshibiao/article/details/28661223		
#define MAXN 105
#define INF 1e+6
#define eps 1e-9
double R[MAXN][MAXN] = {}, V[MAXN] = {}; // R: resist, V: voltage
double f[MAXN][MAXN] = {}; // function need solved;
int main() {
    int N, A, B;
    int x, y, l;
    int cases = 0;
    double w;
    char s1[105], s2[105];
    while(scanf("%d %d %d", &N, &A, &B) == 3) {
        if(N == 0)
            break;
        map<int, int> label;
        l = label[A];
        if(l == 0)	label[A] = label.size();
        A = label[A];
        
        l = label[B];
        if(l == 0)	label[B] = label.size();
        B = label[B];
        
        memset(R, 0, sizeof(R));
        memset(V, 0, sizeof(V));
        memset(f, 0, sizeof(f));
        vector<double> g[MAXN][MAXN];
        for(int i = 0; i < N; i++) {
            scanf("%d %d %lf", &x, &y, &w);
            
            l = label[x];
            if(l == 0)	label[x] = label.size();
            x = label[x];
            
            l = label[y];
            if(l == 0)	label[y] = label.size();
            y = label[y];
            
            g[x][y].push_back(w);
            g[y][x].push_back(w);
        }
        N = label.size();
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                if(g[i][j].size()) {
                    double r = 0;
                    for(int k = 0; k < g[i][j].size(); k++) {
                        r += 1.0 / g[i][j][k];
                    }
                    R[i][j] = 1.0 / r;
                }
            }
        }
        V[A] = INF, V[B] = 0;
        for(int i = 1; i <= N; i++) {
            if(i == A)	continue;
            if(i == B)	continue;
            if(R[i][A] > 0)
                f[i][i] -= 1.0 / R[i][A], f[i][N + 1] -= V[A] / R[i][A];
            if(R[i][B] > 0)
                f[i][i] -= 1.0 / R[i][B], f[i][N + 1] -= V[B] / R[i][B];
            for(int j = 1; j <= N; j++) {
                if(R[i][j] > 0 && i != j && j != A && j != B)
                    f[i][j] = 1.0 / R[i][j], f[i][i] -= 1.0 / R[i][j];
            }
        }
        // Gaussian Elimination
        for(int i = 1; i <= N; i++) {
            int k = i;
            for(int j = i + 1; j <= N; j++)
                if(f[j][i] > 0)
                    k = j;
            if(fabs(f[k][i]) < eps)
                continue;
            for(int j = 1; j <= N + 1; j++)
                swap(f[i][j], f[k][j]);
            for(int j = 1; j <= N; j++) {
                if(i == j)	continue;
                for(int k = N + 1; k >= i; k--)
                    f[j][k] = f[j][k] - f[j][i] / f[i][i] * f[i][k];
            }
        }
        for(int i = 1; i <= N; i++) {
            if(i == A)	continue;
            if(i == B)	continue;
            if(fabs(f[i][i]) > eps)
                V[i] = f[i][N + 1] / f[i][i];
        }
        
        double IB = 0;
        for(int i = 1; i <= N; i++)
            if(R[i][B] > 0)
                IB += V[i] / R[i][B];
        if(fabs(IB) < eps)
            printf("Case %d: %.2lf Ohms\n", ++cases, 0);
        else
            printf("Case %d: %.2lf Ohms\n", ++cases, (V[A] - V[B]) / IB);
    }
    return 0;
}