P2011 - 计算电压题解 - JustPureH2O的博客

您已获得最佳的阅读体验！

题目地址：P2011

题目难度：省选/NOI-

现给定一个电阻网络，已知其中每条边上的电阻，和若干个点和负极之间的电压（电源电压不变），现在求任意两点之间的电压。

对于的数据，，，，。

要解决这道题，我们首先要明白一个定理，即电流定律（，或称第一定律）。定理内容如下：

电路中任意一个节点上，在任何时刻，流入这个节点的电流之和等于流出这个节点的电流之和。

于是我们把每一个接线柱分开来看。假如当前在讨论接线柱，假设电流从若干接线柱流出并流入，那么记为这些接线柱的集合；相应地，如果电流从流出，并流入另一些接线柱，那么记这些接线柱的集合为。此时根据欧姆定律有如下关系：

发现此时又要求每个电阻丝的电压，非常的麻烦。根据高中知识可得，导体两端的电压其实就等于它两端的电势之差，假如电阻丝左右分别连接着接线柱，那么。上式转化为：

发现最后的这个方程式可以使用高斯消元来解决，在系数矩阵中分别填入，作为系数。此时需要注意，第项的系数应是。对于题目中已经给定的值，即直接与正极相连的接线柱只需要列出形如的方程即可。不难发现方程组有条方程，个未知数，是一定有解的。题目的询问就可以转化成求两接线柱之间的电势差了。

#include <bits/stdc++.h>

#define N 210
using namespace std;

typedef pair<int, double> PID;

const double EPS = 1e-12;

vector<PID> G[N];

double matrix[N][N];
double voltage[N];
double start[N];

int gauss(int n) {
    int rank = 0;
    for (int c = 0, r = 0; c <= n; c++) {
        int t = r;
        for (int i = r; i <= n; i++) {
            if (abs(matrix[i][c]) > abs(matrix[t][c])) t = i;
        }
        if (abs(matrix[t][c]) < EPS) continue;
        if (t ^ r) swap(matrix[t], matrix[r]);
        for (int i = n + 1; i >= c; i--) matrix[r][i] /= matrix[r][c];
        for (int i = 0; i <= n; i++) {
            if (abs(matrix[i][c]) > EPS && i ^ r) {
                for (int j = n + 1; j >= c; j--) {
                    matrix[i][j] -= matrix[i][c] * matrix[r][j];
                }
            }
        }
        r++;
        rank++;
    }
    for (int i = 0; i <= n; i++) voltage[i] = matrix[i][n + 1];
    return 2;
}

void out(int n) {
    cerr << "------------------" << endl;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n + 1; j++) {
            cerr << fixed << setprecision(2) << setw(10) << matrix[i][j];
        }
        cerr << endl;
    }
    cerr << "------------------" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, m, k, q;
    cin >> n >> m >> k >> q;
    while (k--) {
        int u;
        cin >> u >> start[u];
    }
    while (m--) {
        int u, v;
        double w;
        cin >> u >> v >> w;
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }
    matrix[0][0] = 1.0;
    for (int i = 1; i <= n; i++) {
        double sum = 0.0;
        if (abs(start[i]) > EPS) {
            matrix[i][i] = 1.0;
            matrix[i][n + 1] = start[i];
            continue;
        }
        for (auto p: G[i]) {
            int u = p.first;
            matrix[i][u] += 1.0 / p.second;
            sum += 1.0 / p.second;
        }
        matrix[i][i] = -sum;
    }
    gauss(n);
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << fixed << setprecision(2) << voltage[u] - voltage[v] << endl;
    }
    return 0;
}

~~说句闲话：第一学月物理考试彻底炸了……诺贝尔物理学奖颁给了机器学习……我在这里写信息学物理题题解……~~

P2011 - 计算电压 题解

P2011 - 计算电压题解