P2011 - 计算电压 题解

1
#include <bits/stdc++.h>
2

3
#define N 210
4
using namespace std;
5

6
typedef pair<int, double> PID;
7

8
const double EPS = 1e-12;
9

10
vector<PID> G[N];
11

12
double matrix[N][N];
13
double voltage[N];
14
double start[N];
15

16
int gauss(int n) {
17
    int rank = 0;
18
    for (int c = 0, r = 0; c <= n; c++) {
19
        int t = r;
20
        for (int i = r; i <= n; i++) {
21
            if (abs(matrix[i][c]) > abs(matrix[t][c])) t = i;
22
        }
23
        if (abs(matrix[t][c]) < EPS) continue;
24
        if (t ^ r) swap(matrix[t], matrix[r]);
25
        for (int i = n + 1; i >= c; i--) matrix[r][i] /= matrix[r][c];
26
        for (int i = 0; i <= n; i++) {
27
            if (abs(matrix[i][c]) > EPS && i ^ r) {
28
                for (int j = n + 1; j >= c; j--) {
29
                    matrix[i][j] -= matrix[i][c] * matrix[r][j];
30
                }
31
            }
32
        }
33
        r++;
34
        rank++;
35
    }
36
    for (int i = 0; i <= n; i++) voltage[i] = matrix[i][n + 1];
37
    return 2;
38
}
39

40
void out(int n) {
41
    cerr << "------------------" << endl;
42
    for (int i = 0; i <= n; i++) {
43
        for (int j = 0; j <= n + 1; j++) {
44
            cerr << fixed << setprecision(2) << setw(10) << matrix[i][j];
45
        }
46
        cerr << endl;
47
    }
48
    cerr << "------------------" << endl;
49
}
50

51
int main() {
52
    ios::sync_with_stdio(false);
53
    cin.tie(nullptr);
54
    cout.tie(nullptr);
55

56
    int n, m, k, q;
57
    cin >> n >> m >> k >> q;
58
    while (k--) {
59
        int u;
60
        cin >> u >> start[u];
61
    }
62
    while (m--) {
63
        int u, v;
64
        double w;
65
        cin >> u >> v >> w;
66
        G[u].emplace_back(v, w);
67
        G[v].emplace_back(u, w);
68
    }
69
    matrix[0][0] = 1.0;
70
    for (int i = 1; i <= n; i++) {
71
        double sum = 0.0;
72
        if (abs(start[i]) > EPS) {
73
            matrix[i][i] = 1.0;
74
            matrix[i][n + 1] = start[i];
75
            continue;
76
        }
77
        for (auto p: G[i]) {
78
            int u = p.first;
79
            matrix[i][u] += 1.0 / p.second;
80
            sum += 1.0 / p.second;
81
        }
82
        matrix[i][i] = -sum;
83
    }
84
    gauss(n);
85
    while (q--) {
86
        int u, v;
87
        cin >> u >> v;
88
        cout << fixed << setprecision(2) << voltage[u] - voltage[v] << endl;
89
    }
90
    return 0;
91
}