题目背景
相信不少人轻松灭掉 1,2 两题（蒟蒻无视此句） ，我相信，大家对物理也是很有兴趣的（众人：我们对揍人也是很有兴趣的） ，那么，再奉上 100 分给Physicaler 们。
题目描述
现给定一个电阻网络，已知其中每条边上的电阻，和若干个点和负极之间的电压（电源电压不变） ，现在求任意两点之间的电压。
输入格式
第一行三个数n,m,k,q，表示n个节点（可能是几个点用导线相连接，与一个点等价，编号为1-n，0号节点为电源负极），m个定值电阻，每个定值电阻连接两个点，k表示电源正极有k个接口，有q个询问。
以下k行，每行两整数，表示电源这k个正极的编号与该接线柱与电源负极负极之间的电压Ui。
以下m行，每行三个数，Vi,Wi,Ri，表示Ui与Vi之间添加一条阻值为R的电阻丝。
以下q行，每行两个整数Ai,Bi，表示要求Ai Bi之间的电压。
输出格式
q 行，每行一个实数，保留小数点后两位。（若 A 点电压低于 B 点，输出负值）
输入输出样例
输入 #1
|
1 2 3 4 5 6 7 8 9 10 |
3 5 1 3 1 18 1 2 6 1 3 2 2 3 6 3 0 6 2 0 2 1 0 2 3 1 2 |
输出 #1
|
1 2 3 |
18.00 -6.00 12.00 |
说明/提示
【数据范围】
对于10%的数据，q=1;
对于20%的数据，1≤n≤10,保证电路为串联,并联或混联;
对于40%的数据，1≤n≤40,k≤5;
对于100%的数据，1≤k≤n≤200,1≤m≤200,000,1≤Ri,Ui≤10,000,1≤q≤1,000,000.
【限制】
时间限制：2s，内存限制：256M
【注释】
样例如图所示
\(首先先把电源负极定义为n+1，根据基尔霍夫方程组，对每个结点u，有第u个方程\)
\(若u是电源正极，那么方程为\varphi_{u}-\varphi_{n+1}=U\)
\(若u不是电源正极，那么方程为\sum_{u, v}\frac{\varphi_{u}-\varphi_{v}}{R_{u, v}}=0\)
\(若u是电源负极，那么方程为\varphi_{n+1}=0\)
\(总共n+1个方程，n+1个未知数，用高斯消元就可以解决\)
|
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 |
#include<stdio.h> #include<iostream> #include<math.h> #define MAXN 210 #define MAXM 400010 #define eps 1e-8 using namespace std; struct Edge { int u, v, next; double r; } e[MAXM]; int n, m, k, q, h[MAXN], pe[MAXN]; double matrix[MAXN][MAXN], p[MAXN]; void addEdge(int u, int v, int r, int num) { e[num].u = u; e[num].v = v; e[num].r = r; e[num].next = h[u]; h[u] = num; } void initMatrix() { for (int u = 1; u <= n; ++u) { if (!pe[u]) { for (int i = h[u]; i; i = e[i].next) { if (fabs(e[i].r) > eps) { matrix[u][u] += 1.0/e[i].r; matrix[u][e[i].v] -= 1.0/e[i].r; } else { matrix[u][u] += 1.0/eps; matrix[u][e[i].v] -= 1.0/eps; } } } else { matrix[u][u] = 1; matrix[u][n+1] = -1; matrix[u][n+2] = p[u]; } } matrix[n+1][n+1] = 1; } int Gauss() { for (int i = 1, r; i <= n+1; ++i) { r = i; for (int j = i+1; j <= n+1; ++j) r = fabs(matrix[j][i]) > fabs(matrix[r][i]) ? j : r; if (fabs(matrix[r][i]) < eps) return 0; if (r != i) for (int j = 1; j <= n+2; ++j) swap(matrix[i][j], matrix[r][j]); for (int j = 1; j <= n+1; ++j) { if (j != i) { double x = matrix[j][i]/matrix[i][i]; for (int k = i+1; k <= n+2; ++k) matrix[j][k] -= x*matrix[i][k]; } } } for (int i = 1; i <= n; ++i) matrix[i][n+2] /= matrix[i][i]; return 1; } int main() { scanf("%d%d%d%d", &n, &m, &k, &q); for (int i = 1, u; i <= k; ++i) { double phi; scanf("%d%lf", &u, &phi); p[u] = phi; pe[u] = 1; } for (int i = 1, u, v; i <= m; ++i) { double r; scanf("%d%d%lf", &u, &v, &r); if (!v) v = n+1; if (!u) u = n+1; addEdge(u, v, r, i); addEdge(v, u, r, i+m); } initMatrix(); if (Gauss()) for (int i = 1; i <= n; ++i) p[i] = matrix[i][n+2]; for (int i = 1, u, v; i <= q; ++i) { scanf("%d%d", &u, &v); printf("%.2lf\n", p[u]-p[v]); } return 0; } |
lzy 说：
您太厉害了，所以这个网站是您自己创的吗
SeaForm 说：
是的qwq