logo AlgoBeat OnlineJudge
登录 注册

#102307. [BZOJ 2307] [Ctsc2011]无穷图的桥

内存限制:128 MiB 时间限制:30000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

本题的目标是求一个点数无穷的无向图的桥。这个无向图具有如下性质:

  1. 这个图是一个连通图
  2. 这个图的所有节点分为若干层,分别是第 层、第 层、第 共有无穷层,每层共有 个节点。为了描述方便,以下用 表示第 层的 号节点。
  3. 同一层内的节点可以相互连边,相邻两层的节点之间可以相互连边,除此之外,其他节点之间不能相互连边。
  4. 如果 之间有一条权值为 的边,那么 之间也有一条边,它的权值为 ,其中 j 为任意正整数。
  5. 如果 之间有一条权值为 的边,那么 之间也有一条边,它的权值为 ,其中 为任意正整数。

如下所示的无向图就符合上面的所有性质。

Failed loading image.

一个点数无穷的无向图是连通的,当且仅当对于图中的任意两个节点都存在一条路径将它们连接起来。而一条边是桥,当且仅当这条边被删去后整个图不连通

请你编写程序读入这个点数无穷的连通图,求出其中所有桥的权值之和。例如,在上图中,粗线所示的边就是该图唯一的桥,因此上图中桥的权值之和为

输入格式

输入第一行包括三个由空格隔开的非负数
从第 行到第 行,每行有三个正整数 ,表示 之间有一条权值为 的边。
从第 行到第 行,每行有三个正整数 ,表示 之间有一条权值为 的边。每行的三个整数之间都用一个空格隔开。
图中两个点 之间可能有多于 条边连接,一条边连接的两个节点可能相同。

输出格式

输出只有一行,包含一个实数,即所有桥的权值之和,四舍五入保留两位小数。

样例

样例输入 #1

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

样例输出 #1

1.00

样例说明 1

这就是问题描述中所举的例子。

样例输入 #2

1 1 1
1 1 100
1 1 1

样例输出 #2

10.00

数据范围与提示

数据编号
1
2
3
4~7
8~10

对于 的数据,

Day2