3459: Maximum Weighted Matching
内存限制：64 MB
时间限制：4.000 S
评测方式：文本比较
命题人：
提交：2
解决：2
题目描述
Chiaki is good at generating special graphs. Initially, she has a graph with only two vertices connected by an edge. Each time, she can choose an edge (u,v), make a copy of it, insert some new vertices (maybe zero) in the edge (i.e. let the new vertices be t1,t2,…,tk, Chiaki would insert edges (u,t1), (t1,t2), (tk−1,tk), (tk,v)into the graph).
Given a weighted graph generated by above operations, Chiaki would like to know the maximum weighted matching of the graph and the number different maximum weighted matchings modulo (109+7)).
A matching in a graph is a set of pairwise non-adjacent edges, none of which are loops; that is, no two edges share a common vertex.
A maximum weighted matching is defined as a matching where the sum of the values of the edges in the matching have a maximal value.
Given a weighted graph generated by above operations, Chiaki would like to know the maximum weighted matching of the graph and the number different maximum weighted matchings modulo (109+7)).
A matching in a graph is a set of pairwise non-adjacent edges, none of which are loops; that is, no two edges share a common vertex.
A maximum weighted matching is defined as a matching where the sum of the values of the edges in the matching have a maximal value.
输入
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains two integers n and m (1≤n,m≤105) -- the number of vertices and the number of edges.
Each of the next m lines contains three integers ui, vi and wi (1≤ui,vi≤n,1≤wi≤109) -- deonting an edge between ui and vi with weight wi.
It is guaranteed that neither the sum of all n nor the sum of all m exceeds 106.
The first line contains two integers n and m (1≤n,m≤105) -- the number of vertices and the number of edges.
Each of the next m lines contains three integers ui, vi and wi (1≤ui,vi≤n,1≤wi≤109) -- deonting an edge between ui and vi with weight wi.
It is guaranteed that neither the sum of all n nor the sum of all m exceeds 106.
输出
For each test case, output two integers separated by a single space. The first one is the sum of weight and the second one is the number of different maximum weighted matchings modulo (109+7).
样例输入 复制
2
6 7
1 2 1
2 3 1
4 5 1
5 6 1
1 4 1
2 5 1
3 6 1
4 5
1 2 1
1 3 1
1 4 1
2 3 1
3 4 1
样例输出 复制
3 3
2 2