HDU 6041 I Curse Myself （仙人掌图）

HDU 6041 I Curse Myself （仙人掌图）

Description

There is a connected undirected graph with weights on its edges. It is guaranteed that each edge appears in at most one simple cycle.Assuming that the weight of a weighted spanning tree is the sum of weights on its edges, define V(k) as the weight of the k-th smallest weighted spanning tree of this graph, however, V(k)Please calculate (∑Kk=1k⋅V(k))mod 232

Input

The input contains multiple test cases.For each test case, the first line contains two positive integers n,m(2≤n≤1000,n−1≤m≤2n−3)Each of the next m lines contains three positive integers x,y,z(1≤x,y≤n,1≤z≤106)The last line contains a positive integer K(1≤K≤105)

Output

For each test case, output “Case #x: y” in one line (without quotes), where x indicates the case number starting from 1 and y denotes the answer of corresponding case.

Sample Input

4 31 2 11 3 21 4 313 31 2 12 3 23 1 346 71 2 41 3 23 5 71 5 32 4 12 6 26 4 57

Sample Output

Case #1: 6Case #2: 26Case #3: 493

题意

求一棵无向仙人掌图中前 k

思路

首先我们需要清楚什么是无向仙人掌图，它是一张连通图，且任意一条边都至多属于一个环。

也就是说，仙人掌图的一棵生成树就是其每个环去掉一条边所形成的图。

那么我们可以一次通过 dfs 找出所有环，然后存储每个环中的所有边长，此时问题就变成了在 n 个数组中各取一个数，求其和的前 k

PS：在最后求解前 k 大的和时千万不要用 O(n3)

AC 代码

#include#include#include#include#include#include#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。