P3617 电阻网络

· · 题解

突然发现这道题居然没人写题解，既然这样那我就水贡献一篇题解吧。
顺便一提，感觉这道题的题面有点模糊且不标准。

题目概要

给定一个电路，其中有n个接线柱和m个电阻，其中阻值只有0和1\Omega两种情况。我们需要求出整个电路从接线柱1到接线柱n的等效电阻值。

题目分析

观察题目描述，我们可以看到四个规则：

  1. 电路只由导线和阻值为1的电阻组成。
  2. 保证电路从左到右连接，保证给出的两个接点x和y符合x<y。
  3. 保证接线柱1为电源正极，接线柱n为电源负极。
  4. 保证每个接线柱只会被串联或者并联两个分支电路或者不接任何电线或电阻。

看到以上条件不难得到，任意一个电阻或导线上的电流一定是从接线柱x流向接线柱y的。再观察题目背景中的信息，画出图来，我们会发现任何一个接线柱的出度都不大于2。那么以电流方向为有向图的方向，以接线柱为节点，以边为电阻或导线建立出一个有向图（根据题目描述，图中一定没有环）。

题解部分

我们考虑使用递归方式合并当前接线柱连接的子电路为一个等效电阻，然后将两个电阻合并为一个电阻。

建图

首先还是给出结构体的代码吧：

struct Link { // 一个电阻连接
    int to; // 连接到的接线柱编号
    double r; // 阻值
};
struct Node { // 一个接线柱
    int linkCount = 0;
    Link links[2];
} node[100005];

建图部分代码将在最后给出。

合并电阻

这里是最难也最核心的部分了，我们先设计出一个可能的函数原型：

void mergeSubcricut(int p, int e)

其中“接线柱p”为我们要合并的电路的正极，“接线柱e”为电路的负极。我们就先假设这个函数可以把“接线柱p”到“接线柱e”中间的电路合并成一个等效电阻。

串联


在这里“子电路a”（这里确定是一个电阻或导线）与“子电路b”（可能是复合电路）串联。“子电路a”的阻值已知，我们只需要再合并“子电路b” 为一个等效电阻即可。 

if(node[p].linkCount == 1) {
        // 如果下一个是e（终点），我们就返回
        if(node[p].links[0].to == e) return;
        // 递归合并下一个接线柱的子电路
        mergeSubcricut(node[p].links[0].to, e);
        // 下一个接线柱的子电路已经被合并成了一个电阻
        // 计算两段的电阻，并合并两个电阻
        node[p].links[0].r += node[node[p].links[0].to].links[0].r;
        node[p].links[0].to = node[node[p].links[0].to].links[0].to;
    }

合并完成后，将两个电路的电阻相加，即为“接线柱p”到“接线柱e”的等效电阻阻值。

如果“接线柱p”的下一个接线柱就是“接线柱e”，那么说明这中间一段的电路已经被合并成了一个等效电阻了，不需要合并了，此时应直接返回。

并联

这种情况比较麻烦，我们需要分别合并“子电路a2”和“子电路b2”，但是我们发现，两者的汇聚点并不在“接线柱e”上。

在这种情况下，我们就需要获取到获取到并联电路的汇点（假定为“接线柱ep”），然后单独把“子电路a2”到“接线柱ep”的部分和“子电路b2”到“接线柱ep”的部分跑一遍合并。因为编号大的一定在编号小的接线柱的前面，所以可以通过比较深度来比较两个点的“深度”。

int endPoint(int a, int b) {
    // printf("Finding End Point of %d %d\n", a, b);
    // 由于编号大的一定在右边，可以通过比较编号找到两个点往后走的终结点
    while (a != b) {
        if(a > b) {
            b = node[b].links[0].to;
        } else {
            a = node[a].links[0].to;
        }
    }
    return a;
}

合并后的情况如下：

这里就可以很容易地把“子电路a1,a2”和“子电路b1,b2”分别合并成两个等效电阻了，合并后根据初中的并联电路计算公式计算即可：

R=\frac{R_1R_2}{R_1+R_2}

合并后的图像如下：


这里我们会发现，整个电路变成和串联一样的情况了！

既然这样，我们只需要在执行完以上合并流程后，重新跑一遍从“接线柱p”到“接线柱e”的合并即可。这样就可以把这一部分电路合并成一个等效电阻了。

至此，所有的函数执行工作就结束了，在构建完成之后，我们只需要用这个函数将整个电路合并成一个电阻：

mergeSubcricut(1, n);

最后输出这个等效电阻的阻值即可。

所有的内容的具体的实现代码在这里给出：

AC代码

/* Headers */
#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
using namespace std;
/* Type and variables */
int n, m;
struct Link { // 一个电阻连接
    int to;
    double r; // 电阻
};
struct Node { // 一个接线柱
    int linkCount = 0;
    Link links[2];
} node[100005];
/* Functions */

int endPoint(int a, int b) {
    // printf("Finding End Point of %d %d\n", a, b);
    // 由于编号大的一定在右边，可以通过比较编号找到两个点往后走的终结点
    while (a != b) {
        if(a > b) {
            b = node[b].links[0].to;
        } else {
            a = node[a].links[0].to;
        }
    }
    return a;
}
// 合并从p到e的子电路
void mergeSubcricut(int p, int e) {
    if(p == e) return; // 同一个接线柱就不需要合并了
    if(node[p].linkCount == 1) {
        // 如果下一个是e（终点），我们就返回
        if(node[p].links[0].to == e) return;
        // 递归合并下一个接线柱的子电路
        mergeSubcricut(node[p].links[0].to, e);
        // 下一个接线柱的子电路已经被合并成了一个电阻
        // 计算两段的电阻，并合并两个电阻
        node[p].links[0].r += node[node[p].links[0].to].links[0].r;
        node[p].links[0].to = node[node[p].links[0].to].links[0].to;
    } else if(node[p].linkCount == 2) {
        int subEnd = endPoint(node[p].links[0].to, node[p].links[1].to);
        // 分别递归合并下面两个接线柱的子电路
        mergeSubcricut(node[p].links[0].to, subEnd);
        mergeSubcricut(node[p].links[1].to, subEnd);
        // 下两个接线柱的子电路已经被合并成了两个电阻
        node[p].links[0].r += node[node[p].links[0].to].links[0].r;
        node[p].links[0].to = node[node[p].links[0].to].links[0].to;
        node[p].links[1].r += node[node[p].links[1].to].links[0].r;
        node[p].links[1].to = node[node[p].links[1].to].links[0].to;
        node[p].linkCount = 1;
        // 计算电阻
        node[p].links[0].r = (node[p].links[0].r * node[p].links[1].r) / (node[p].links[0].r + node[p].links[1].r);
        // 考虑两个电阻阻值都为0的情况
        if(node[p].links[0].r + node[p].links[1].r < 0.0000001)
            node[p].links[0].r = 0.0;
        mergeSubcricut(p, e);
    }
}
/* Main */
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++) {
        int u, v; double r;
        scanf("%d%d%lf", &u, &v, &r);
        node[u].links[node[u].linkCount++] = {v, r};
    }
    mergeSubcricut(1, n); // 合并从1到n的电路
    printf("%.3f", node[1].links[0].r);
    return 0;
}