P6327: 「ZJOI2016」电阻网络

---

【题目描述】

小 Y 是一个充满智慧的女孩子，但是她只会使用串并联的方法计算两个节点之间的电阻。 现在小 Y 有一个电阻网络，问有多少点对 $u,v(u\ne v)$ 之间的电阻可以用串并联的方法计算出来。 我们来形式化地定义一下点对 $u,v(u\ne v)$ 之间的电阻能用串并联的方法计算出来的条件。首先我们把电阻网络看成一个 $n$ 个点 $m$ 条边的图（每个电阻对应一条边）。令 $S$ 表示从 $u$ 到 $v$ 的所有简单路径（不经过重复的点的路径）上点的并集，也就是对于一个点 $x$，如果存在一条从 $u$ 到 $v$ 的简单路径经过这个点，那么它就在集合 $S$ 中。如果 $S$ 非空且 $S$ 的导出子图是 $u,v$ 为端点的二端串并联图，那么 $u,v$ 之间的电阻就能用串并联方法计算。

1. 一个有两个不同端点 $s,t$ 的图被称为二端图，其中一个称为源点，另一个称为汇点。
2. 两个二端图 $X,Y$ 并联 (parallel composition) 是指建一个新图，把 $X$ 和 $Y$ 的源点和汇点分别合并起来。
3. 两个二端图 $X,Y$ 串联 (series composition) 是指建一个新图，把 $X$ 的汇点和 $Y$ 的源点合并起来。
4. 由若干个两个点一条边的二端图经过一系列串并联变化之后形成的图称为二端串并联图。

集合 $S$ 的导出子图点集为 $S$，边集由原图中两个端点都在 $S$ 中的边构成。

【输入】

【输出】

【提示】

题目类型~

ZJOI2016 NOIP 省选 高级 

咻咻~

提交答案 状态 返回