首页 > 试题广场 >

Enumeration not optimization

[编程题]Enumeration not optimization
Niuniu is (p)reviewing NOIP 2017 problems.
Maybe you have heard NOIP 2017 Day 2 Problem 2 Treasure.
You can find the problem at https://www.nowcoder.com/acm/contest/154/1002.
He found that the official data is very weak. Many contestants accepted this problem with search solutions or wrong solutions.

Let's consider the enumeration version of this problem.
We want to find the sum of weight of all rooted spanning tree.
The weight of a rooted spanning tree is defined as follows.

Enumerate all edges in the tree.
The contribution of an edge is its weight times its depth in the rooted tree.

The depth of a vertex is the number of edges from the root to the vertex.

As the answer might be very large, you only need to output the answer mod 1000000007.


输入描述:
The first line contains two integers n, m, which are the number of vertices and the number of edges.
In the following m lines, each line contains three integers x, y, z, which means there is an edge between x and y, whose weight is z.

1 <= n <= 12
1 <= m <= 1000
1 <= x <= n
1 <= y <= n
1 <= z <= 5000


输出描述:
You should ouput one line, which contains the answer.
示例1

输入

4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 1

输出

303
示例2

输入

4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 2

输出

336

备注:
There might be multiple edges between two vertices.
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

深度优先搜索(DFS) 动态规划 树
难度：
0条回答 17浏览

热门推荐

通过挑战的用户

查看代码

相关试题

Enumeration not optimization

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号