HDU 6036 I Curse Myself 仙人掌的最小生成树

http://acm.hdu.edu.cn/showproblem.php?pid=6041

I Curse Myself

Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)

Problem 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)$ would be defined as zero if there did not exist $k$ different weighted spanning trees.
Please calculate $\displaystyle\left(\sum_{k=1}^{K}{k \cdot V(k)}\right) \bmod 2^{32}$.

Input

The input contains multiple test cases.
For each test case, the first line contains two positive integers $n, m$ $(2 \leq n \leq 1000, n-1 \leq m \leq 2n-3)$, the number of nodes and the number of edges of this graph.
Each of the next $m$ lines contains three positive integers $x, y, z$ $(1 \leq x, y \leq n, 1 \leq z \leq 10^6)$, meaning an edge weighted $z$ between node $x$ and node $y$. There does not exist multi-edge or self-loop in this graph.
The last line contains a positive integer $K$ $(1 \leq K \leq 10^5)$.

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

Sample Output

Source

 

题意

给一个$n$个点的无向图,保证一条边最多属于一个环,求前$k$小生成树的权重*排名的和。

思路

可以发现这是一颗仙人掌图,对于每一个环来说,最小生成树上会不包含上面的一条边。换句话说,边权的总和,减去每个环上的一条边,就是一颗生成树。那么就是每个环贡献一条边,求这些边和前$k$大值。考虑这$m$个环上的边,构成了$m$个数组,我们只需要对数组两两合并,维护前$k$大值即可。合并的时候采用优先队列,将长度短的数组的每一个数$b_i + a_0$放入优先队列,弹出的时候,记录答案,修改$a$元素为较大的一个后继续放入优先队列(这里$a$数组已经排序)。

 

 

 
 

发表评论

电子邮件地址不会被公开。 必填项已用*标注