编程介的小学生
2019-02-27 17:51一个二分图的遍历搜索方面的问题,如何运用C语言的技术解答这个问题的
Problem Description
Brian's little sister Mary is fond of strange games involving lots of calculation. Unfortunately she's not so good at mathematics so Brian's often asked to calculate the values needed for her. Recently Brian's facing another such problem:
An undirected graph with N vertexes and M edges is first drawn by Mary. Then, Mary randomly assigns an integer value to each of the vertexes. After that, Mary will perform a sequence of operations on the graph, each operation being of one of the following type:
a) Among all vertexes connecting with vertex X via some edges, find the least value that is no less than value K. If such value cannot be found, zero will be returned instead.
b) Updates the value assigned to vertex X to K.
c) Erases an edge connecting vertex A and B from the graph.
Mary’s interested in the average value of all answers to type a) operations. Would you please help Brian to finish this boring task?
Input
There are multiple test cases in the input file. Each case starts with three integers, N, M, and Q (1 <= N <= 2 * 104, 0 <= M <= 6 * 104, 1 <= Q <= 3 * 105). The next N lines describe the initial value assigned to each vertex. The next part of each test case consists of M lines, and describes the edges in the graph at the beginning. Vertexes are numbered from 1 to N. The last part of each test case describes the operations to be performed on the tree. For operations of a) type, a line similar to “F X K” will be given; for operations of b) type, a line with the format of “U X K” will be given; and for c) type, the description will be given in the format similar to “E A B”. You can assume that there will always be at least one a) type query. The absolute value assigned to any vertex at any time will not exceed 10000.
There is a blank line between two successive cases. Input ends with End-of-File.
Output
For each test case, output one real number – the requested value with precision up to 0.001, in the format as indicated in the sample output.
Sample Input
3 3 8
4
5
8
1 2
2 3
1 3
F 1 4
E 1 3
F 2 7
E 2 3
E 1 2
F 2 7
U 3 6
F 3 3
1 0 1
0
F 1 0
Sample Output
Case 1: 4.500
Case 2: 0.000
- 点赞
- 回答
- 收藏
- 复制链接分享
0条回答
为你推荐
- 一个节点数的计算和遍历的问题,广度优先搜索,采用C语言的实现方式
- r语言
- Golang
- erlang
- 1个回答
- 连续的图的遍历算法,用回溯怎么实现编写,C语言的谢谢
- r语言
- Golang
- erlang
- 1个回答
- 数据结构如何遍历一个树上的边的算法
- lines
- 遍历
- 算法
- Golang
- 1个回答
- 图论搜索——如何遍历搜索这个图的算法
- lines
- each
- it
- Golang
- 1个回答
- 请教一个C++链表(linked list)的创建和遍历的基础问题
- linked list
- c++
- 链表
- 2个回答