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 (∑k=1Kk⋅V(k))mod232.
问题 I: I Curse Myself
时间限制: 10 Sec 内存限制: 128 MB提交: 4 解决: 0
[提交][状态][讨论版][命题人:]
题目描述
输入描述
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), 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≤x,y≤n,1≤z≤106), 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≤K≤105).
For each test case, the first line contains two positive integers n,m (2≤n≤1000,n−1≤m≤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≤x,y≤n,1≤z≤106), 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≤K≤105).
输出描述
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.
样例输入
4 3
1 2 1
1 3 2
1 4 3
1
3 3
1 2 1
2 3 2
3 1 3
4
6 7
1 2 4
1 3 2
3 5 7
1 5 3
2 4 1
2 6 2
6 4 5
7
样例输出
Case #1: 6
Case #2: 26
Case #3: 493
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
cnt: 43771
关于网站改版