poj 3532 Resistance

---恢复内容开始---

Resistance

Time Limit: 1000MS		Memory Limit: 131072K
Total Submissions: 1289		Accepted: 418

Description

H.L. is preparing a circuit for the next coming physical experiment. His circuit consists of N nodes, numbered 1 to N, which are connected by wires with certain resistance. H.L is curious about the equivalent resistance between Node 1 and Node N.

Input

The first line contains two positive integers N and M, the number of nodes and wires in the circuit.( N, M ≤ 100)
The next M lines, each describe a wire connection by three integers X, Y, R which indicates that between Node X and Node Y, there is a wire with resistance of R ohm.

Output

The equivalent resistance rounded after the second decimal place.

Sample Input

Sample Output

0.50

题意：有N个节点，M条电线，电线都会有电阻，求起始节点和终止节点之间的等效电阻
思路：由基尔霍夫电流定律，每个节点的流入电流与流出电流量是相等的，根据这条信息我们即可列出相关方程。
例如下图，以节点2为例可列方程，I1,I2,I3分别是在单位电势下流经节点(1,2),(2,3),(2,4)之间电线的电流，那么我们设x1,x2,x3,x4分别为节点1，2，3，4的电势，流入节点的电流等于流出节点的电流量，则可得到方程：
I1(x1-x2)+I2(x3-x2)+I3(x4-x2)=0;整理一下：I1x1+(-I1-I2-I3)x2+I2x3+I3x4=0;

那么除了初始节点和终止节点，其余的节点都有上述等式成立，则可得到n-2个方程，初始节点和终止节点的电势，我们可以人为的设置一个值，不如就初始节点电势为1，终止节点电势为0，再根据n-2个方程即可得到中间n-2个节点的电势值。

之后只要求出流经整幅图的电流量I_sum,那么等效电阻=（初始结点电势-终止节点电势）/ I_sum==1 / I_sum。

I_sum可以通过计算初始节点的电流流入量或者终止节点电流流出量得到。

AC代码：

#define _CRT_SECURE_NO_DEPRECATE

#include <iostream>

#include <vector>

#include<algorithm>

#include<cmath>

#include<cstring>

using namespace std;

#define MAX_N 500

#define EPS 1e-8

typedef vector<double> vec;

typedef vector<vec> mat;

double resistor[MAX_N][MAX_N];    // 不考虑其他节点影响时，两个节点间的电阻

int N, M;

vec gauss(const mat&A, const vec&b) {

    int n = A.size();//!!!!

    mat B(n, vec(n + ));

    for (int i = ; i < n; i++)

        for (int j = ; j < n; j++)B[i][j] = A[i][j];

    for (int i = ; i < n; i++)B[i][n] = b[i];

    for (int i = ; i < n; i++) {

        int pivot = i;

        for (int j = i; j < n; j++) {

            if (abs(B[j][i]) > abs(B[pivot][i])) {//!!!

                pivot = j;

            }

        }

        swap(B[i], B[pivot]);

        if (abs(B[i][i]) < EPS)return vec();//无解

        for (int j = i + ; j <= n; j++) {

            B[i][j] /= B[i][i];

        }

        for (int j = ; j < n; j++) {

            if (i != j) {

                for (int k = i + ; k <= n; k++) {

                    B[j][k] -= B[j][i] * B[i][k];

                }

            }

        }

    }

    vec x(n);

    for (int i = ; i < n; i++) {

        x[i] = B[i][n];

    }

    return x;

}

int main() {

    while (scanf("%d%d", &N, &M) != EOF) {

        memset(resistor, , sizeof(resistor));

        for (int i = ; i < M; i++) {

            int from, to;

            double R;

            scanf("%d%d%lf", &from, &to, &R);

            if (R == )continue;

            from--, to--;

            resistor[from][to] +=  / R;

            resistor[to][from] +=  / R;

        }

        for (int i = ; i < N; i++) {

            for (int j = ; j < N; j++) {

                resistor[i][j] = 1.0 / resistor[i][j];

            }

        }

        mat A(N, vec(N, ));

        vec b(N, );

        b[] = 1.0;

        b[N - ] = 0.0;

        A[][] = , A[N - ][N - ] = ;

        for (int i = ; i < N - ; i++) {

            for (int j = ; j < N; j++) {

                if (resistor[i][j] > ) {

                    double I = 1.0 / resistor[i][j];

                    A[i][i] -= I;

                    A[i][j] += I;

                }

            }

        }

        vec voltage = gauss(A, b);

        double current = ;

        for (int i = ; i < N; i++) {

            if (resistor[][i] > ) {

                current += (voltage[] - voltage[i]) / resistor[][i];

            }

        }

        printf("%.2f\n", 1.0 / current);

    }

    return ;

}

巴特西

poj 3532 Resistance

最新文章

热门文章