远端评测题 3000ms 125MiB

[CTSC2011] 无穷图的桥

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

本题的目标是求一个点数无穷的无向图的桥。

这个无向图具有如下性质:

  1. 这个图是一个连通图。

  2. 这个图的所有节点分为若干层,分别是第11层、第22层、第33\cdots共有无穷层,每层共有nn个节点。为了描述方便,以下用(i,x)(i, x)表示第ii层的xx号节点。

  3. 同一层内的节点可以相互连边,相邻两层的节点之间可以相互连边,除此之外,其他节点之间不能相互连边。

  4. 如果(i,x)(i, x)(i,y)(i, y)之间有一条权值为dd的边,那么(j,x)(j, x)(j,y)(j, y)之间也有一条边,它的权值为0.9jid0.9^{j-i}d,其中j为任意正整数。

  5. 如果(i,x)(i, x)(i+1,y)(i + 1, y)之间有一条权值为dd的边,那么(j,x)(j, x)(j+1,y)(j+1, y)之间也有一条边,它的权值为0.9jid0.9^{j-i}d,其中jj为任意正整数。如下所示的无向图就符合上面的所有性质。

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

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

输入格式

输入文件infinite.in第一行包括三个由空格隔开的非负数nnm1m_1m2m_2。从第22行到第m1+1m_1+ 1行,每行有三个正整数xxyydd,表示(1,x)(1, x)(1,y)(1, y)之间有一条权值为d的边。

从第m1+2m_1+ 2行到第m1+m2+1m_1+ m_2+ 1行,每行有三个正整数xxyydd,表示(1,x)(1, x)(2,y)(2, y)之间有一条权值为dd的边。每行的三个整数之间都用一个空格隔开。

图中两个点xxyy之间可能有多于11条边连接,一条边连接的两个节点可能相同。

输出格式

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

3 1 3
1 2 4
1 2 5
2 3 3
3 3 1
1.00
1 1 1
1 1 100
1 1 1
10.00

提示

【样例说明1】

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

【数据规模】 ||||| | :----------- | :----------- | :----------- | :----------- | | 数据编号 | nn | m1m_1 | m2m_2 | | 1 | 10\leq10 | 50\leq50 | 50\leq50 | | 2 | 10000\leq10000 | 40000\leq40000 | 40000\leq40000 | | 3 | 300000\leq300000 | 500000\leq500000 | =1=1 | | 4~7 | 300000\leq300000 | 500000\leq500000 | 500\leq500 | | 8~10 | 300000\leq300000 | 500000\leq500000 | 500000\leq500000 |

100%的数据中,d100d\leq 100

2024.8.6普及集训第四天(追光班)

未参加
状态
已结束
规则
IOI
题目
15
开始于
2024-8-6 8:00
结束于
2024-8-14 16:00
持续时间
200 小时
主持人
参赛人数
30