同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

22571_ReliableNets

2022-5-16 18:22| 发布者: Hocassian| 查看: 23| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-5-89506745989800-Problem List-采集的数据-后羿采集器.html

Pro.ID

22571

Title

Reliable Nets

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=22571

AC

Submit

Ratio

时间&空间限制

Time Limit: 1200/400 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

描述

You’re in charge of designing a campus network between buildings and are very worried about its reliability and its cost. So, you’ve decided to build some redundancy into your network while keeping it as inexpensive as possible. Specifically, you want to build the cheapest network so that if any one line is broken, all buildings can still communicate. We’ll call this a minimal reliable net.

输入

There will be multiple test cases for this problem. Each test case will start with a pair of integers n ( <= 15 ) and m ( <= 20 ) on a line indicating the number of buildings (numbered 1 through n) and the number of potential inter-building connections, respectively. (Values of n = m = 0 indicate the end of the problem.) The following m lines are of the form b1 b2 c (all positive integers) indicating that it costs c to connect building b1 and b2. All connections are bidirectional.

输出

Description

Input

Output

For each test case you should print one line giving the cost of a minimal reliable net. If there is a minimal reliable net, the output line should be of the form:
The minimal cost for test case p is c.
where p is the number of the test case (starting at 1) and c is the cost. If there is no reliable net possible, output a line of the form:
There is no reliable net possible for test case p.

Sample Input

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

Sample Output

The minimal cost for test case 1 is 6.
There is no reliable net possible for test case 2.

Source

East Central North America 2005