一个二分图的遍历搜索方面的问题,如何运用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
数据结构森林的遍历和搜索问题
4
C#遍历treeview节点,以及对应名字文件的内容获取
2
C#如何遍历某个名字节点下的所有子节点名字,
1
一个图的遍历的问题, 使用C语言来做
1
C++语言编程 二叉搜索树 查找
1
如何用c语言实现二叉树
1
一个二叉树的遍历方面的问题求问下各位大神了
1
连续的图的遍历算法,用回溯怎么实现编写,C语言的谢谢
1
图的遍历+节点访问概率计算,一个数据结构怎么使用C语言实现
1
C语言旅行商遍历问题,旅行问题,采用C语言怎么解决?
2
C语言链表插入问题 插入节点到头节点之前去 遍历后发现只能显示插入的那个节点。
1
一个节点数的计算和遍历的问题,广度优先搜索,采用C语言的实现方式
1
DFS算法遍历图,返回上一层的问题。
0
关于遍历一个树的问题,怎么从一个叶子节点跳转到另一个,采用C语言完成
0
线段树的搜索和遍历,线段树相关问题的解决,使用C语言的办法
0
区间整数遍历问题,子序列的遍历怎么使用C语言算法计算实现?
0
符号序列的一次遍历算法ON的问题,利用C语言的编程技术解决
0
数列对的问题,如何运用C语言的方式作答,利用C语言如何解决这个问题
0
广度优先算法遍历一个数据结构里面的图相关的算法运用C语言的实现
0
求问一次遍历搜索要求下如何才能解决这个问题,使用C语言利用的算法的思路