首页 > 试题广场 >

Steiner Tree

[编程题]Steiner Tree
Bobo has a connected undirected simple graph with n vertices and m edges. The vertices are numbered by 1, 2, ..., n conveniently.
Given an integer k, Bobo chooses a subset of edges such that the vertices 1, 2, ..., k can reach each other via the chosen edges. He wants the chosen number of edges is minimized. Find out the number of ways to choose modulo (109+7).


输入描述:
The input consists of several test cases and is terminated by end-of-file.
The first line of each test case contains three integers n, m and k.
The i-th of the following m lines contains 2 integers ai and bi which denote the edge between vertices ai and bi.


输出描述:
For each test case, print an integer which denotes the result.
示例1

输入

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

输出

2
1
1

备注:
* 1 ≤ n ≤ 50
* 
* 
* 1 ≤ ai, bi ≤ n
* The number of test cases does not exceed 100.
* The number of test cases with n > 8 does not exceed 5.
算法知识视频讲解
添加回答

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

提交观点

问题信息

最短路
难度：
0条回答 29浏览

热门推荐

通过挑战的用户

查看代码

相关试题

Steiner Tree

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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