#2324. 电阻网络

    ID: 2324 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>PROV赛事:contest30来源:qoj.ac数据:公开样例并查集

电阻网络

电阻网络

题目描述

NOI2016 浙江省队选拔赛第二试 电阻网络 电阻网络 【问题描述】 小Y 是一个充满智慧的女孩子,但是她只会使用串并联的方法计算两个节 点之间的电阻。 现在小Y 有一个电阻网络,问有多少点对 𝑢, 𝑣 𝑢≠𝑣 之间的电阻可以用串并联的方法计算出 来。 我们来形式化地定义一下点对 𝑢, 𝑣 𝑢≠𝑣 之间 的电阻能否用串并联的方法计算出来。首先我们把电 阻网络看成一个 𝑛 个点 𝑚 条边的图(每个电阻对应一 条边)。令 𝑆 表示从 𝑢 到 𝑣 的所有简单路径(不经过重 复的点的路径)上点的并集,也就是对于一个点 𝑥 ,如 果存在一条从 𝑢 到 𝑣 的简单路径经过这个点,那么它 就在集合 𝑆 中。如果 𝑆 非空且 𝑆 的导出子图是 𝑢, 𝑣 为 端点的二端串并联图,那么 𝑢, 𝑣 之间的电阻就能用串 并联方法计算。 一个有两个不同端点 𝑠, 𝑡 的图被称为二端图,其中一个称为源点,另一个称 为汇点。两个二端图 𝑋, 𝑌 并联(parallel composition)是指建一个新图,把 𝑋 和 𝑌 的 源点和汇点分别合并起来。两个二端图 𝑋, 𝑌 串联(series composition)是指建一个 新图,把 𝑋 的汇点和 𝑌 的源点合并起来。由若干个两个点一条边的二端图经过 一系列串并联变化之后形成的图称为二端串并联图。 集合 𝑆 的导出子图点集为 𝑆 ,边集由原图中两个端点都在 𝑆 中的边构成。 【输入格式】 输入文件circuit.in 第一行包含 2 个正整数 𝑛, 𝑚 ,表示电阻网络中的节点数 和电阻数。 接下来 𝑚 行,每行包含 2 个正整数 𝑢, 𝑣 (1 ≤𝑢, 𝑣≤𝑛, 𝑢≠𝑣) ,表示有一个 电阻在节点 𝑢 和 𝑣 之间。 【输出格式】 输出文件为circuit.out。 输出共 1 行,表示答案,即有多少点对之间的电阻可以使用串并联的方法计 算出来。 【样例输入1】 6 6 1 2

NOI2016 浙江省队选拔赛第二试 电阻网络 1 3 1 4 2 3 2 4 5 6 【样例输出1】 6 【样例解释1】 可行的点对有 1, 2 , 1, 3 , 1,4 , 2,3 , 2,4 , (5,6)。 【样例输入2】 13 18 1 2 2 3 2 4 3 4 3 5 4 5 5 6 5 7 5 8 6 8 7 8 8 9 10 11 10 12 10 13 11 12 11 13 12 13 【样例输出2】 25 【样例输入输出3】 见选手目录下的circuit/circuit_ex1.in 与circuit/circuit_ex1.ans。

NOI2016 浙江省队选拔赛第二试 电阻网络 【样例输入输出4】 见选手目录下的circuit/circuit_ex2.in 与circuit/circuit_ex2.ans。 【数据规模和约定】 各测试点满足以下约定: 测试点 𝑛 m 约定 1 ≤10 ≤10 保证原图连通,并且不存在一个 点删去之后使得原图不连通 2 ≤100 ≤100 3 无 4 ≤103 ≤103 5 ≤105 ≤105 保证原图连通,并且不存在一个 点删去之后使得原图不连通 6 7 8 无 9 10

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

6 6
1 2
1 3
1 4
2 3
2 4
5 6
6

样例 2

13 18
1 2
2 3
2 4
3 4
3 5
4 5
5 6
5 7
5 8
6 8
7 8
8 9
10 11
10 12
10 13
11 12
11 13
12 13
25