P3351 [ZJOI2016]电阻网络

    • 1通过
    • 5提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 SPFA 动态规划,动规,dp 搜索 2016 浙江 高性能
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小Y是一个充满智慧的女孩子,但是她只会使用串并联的方法计算两个节点之间的电阻。现在小Y有一个电阻网络问有多少点对u,v(u≠v)之间的电阻可以用串并联的方法计算出来。

    我们来形式化地定义一下点对u,v(u≠v)之间的电阻能否用串并联的方法计算出来。首先我们把电阻网络看成一个n个点m条边的图(每个电阻对应一条边)。

    令S表示从u到v的所有简单路径(不经过重复的点的路径)上点的并集,也就是对于一个点x,如果存在一条从u到v的简单路径经过这个点,那么它就在集合S中。

    如果S非空且S的导出子图是u,v为端点的二端串并联图,那么u,v之间的电阻就能用串并联方法计算。一个有两个不同端点s,t的图被称为二端图,其中一个称为源点,另一个称为汇点。两个二端图X,Y并联(parallelcomposition)是指建一个新图,把X和Y的源点和汇点分别合并起来。两个二端图X,Y串联(seriescomposition)是指建一个新图,把X的汇点和Y的源点合并起来。由若干个两个点一条边的二端图经过一系列串并联变化之后形成的图称为二端串并联图。

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

    输入输出格式

    输入格式:

    第一行包含2个正整数n,m,表示电阻网络中的节点数和电阻数。接下来m行,每行包含2个正整数u,v(1<=u,v<=n,u≠v),表示有一个电阻在节点u和v之间

    输出格式:

    输出共1行,表示答案,即有多少点对之间的电阻可以使用串并联的方法计算出来。

    输入输出样例

    输入样例#1: 复制
    6 6
    1 2
    1 3
    1 4
    2 3
    2 4
    5 6
    输出样例#1: 复制
    6
    //可行的点对有(1,2),(1,3),(1,4),(2,3),(2,4),(5,6)。

    说明

    n,m<=100000

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。