预测比赛的得分的一个运用题的算法,怎么采用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

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

1
数据结构上的一个线性表的冲突的解决,是不是用哈希算法怎么采用C语言的实现方式
0
比赛场次的划分,使得差距最小的分配算法,采用C语言的程序设计技术
0
求寻找最近的分块的一个算法题,怎么采用C程序语言的编写的技术来实现的。
0
MAP数据结构在搜寻算法的运用,采用C语言的程序的设计的思路解决
1
拍卖竞价的一个应用题的算法的实现,怎么采用C语言的程序的设计的形式来实现的呢
0
一个拼写的检查的程序的一个算法,怎么采用C程序的语言的编写的设计的方式来实现
0
一个绘图填色的算法的计算问题,运用C语言的程序编写程序来实现的办法怎么做
0
迷宫的遍历的算法在数据结构方面的一个运用,怎么采用C程序的语言的技术设计的代码实现?
1
复杂度的一个控制的算法的问题,怎么采用的C语言的程序的编写的过程来实现的?
0
老鼠上楼的一个运用题的算法,在C语言的程序编写的过程的方式?
0
反推递增数列的一个算法的思路问题,怎么采用C语言的程序的设计的思想实现?
0
和最短路经有关的一个时间的算法的运用,怎么采用C语言的程序的编写的过程去实现的
0
藏宝地图遍历的一个算法问题,运用数据结构怎么采用C语言的程序的设计的方式实现?
0
函数递归运算的运用算法问题,怎么采用C语言的程序的设计的思想实现?
0
数据结构字符串数组的一个运用,怎么采用C程序编写的语言的算法实现的程序?
0
追赶公共汽车的一个应用题的算法问题,怎么采用C语言的程序的编写的过程实现的呢?
0
迷宫的绕路的一个算法问题,如何运用C语言的程序的编写的方式实现
0
几何图形的碰撞的一个判断的算法,怎么采用C语言的程序的代码的编写的思路去实现的呢?
0
不同情况下损伤的一个计算算法,运用 C语言的程序的编写的方式是什么的思路?
0
运用数据结构去实现纸牌的移动的一个算法,怎么采用C语言的程序的代码的编写的技术实现的?