Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

用prim的次最小生成树WA的看过来,绝对受益!!!

Posted by 1871168524 at 2014-11-14 21:49:24 on Problem 1679
WA了一天,由于存边时,写挫了,把边的两端点给存变形了,所以一直WA,然后今天晚上,上网上查了下测试数据,才发现。终于AC了。方法很简单,枚举最小生成树上的每一个边,然后删除每条边,重新求最小生成树,与未删边求得的值进行比较,如果一样的,说明答案不唯一,否则输出结果。

下面是测试数据:
9
1 0
4 5
1 2 1
2 3 1
3 4 1
1 4 2
2 4 1
10 15
2 10 97
2 6 18
7 1 63
5 4 62
7 5 93
1 3 10
6 9 99
3 7 73
2 7 6
5 9 22
5 3 82
4 2 36
8 1 50
10 3 20
7 9 69
10 15
10 5 79
4 2 33
4 8 41
9 3 97
5 2 25
2 6 9
2 10 66
8 3 38
10 8 89
1 10 83
1 7 91
7 3 94
7 10 40
7 2 70
2 3 82
10 15
3 8 84
7 10 34
1 10 14
1 9 60
7 6 49
8 5 39
4 5 96
4 7 78
7 3 33
2 8 56
8 9 71
5 2 83
3 6 61
7 9 63
2 6 43
10 15
1 10 25
1 3 14
10 5 72
8 3 18
2 5 41
4 9 86
6 8 17
6 2 98
5 6 34
1 8 90
7 1 65
7 2 63
8 7 71
4 2 64
9 6 50
10 15
2 7 13
5 10 52
5 2 5
10 6 47
9 4 23
8 10 54
1 10 20
4 10 8
6 1 87
8 2 43
8 1 87
6 3 53
3 1 87
2 3 82
4 6 91
10 15
1 2 14
4 1 89
7 6 8
9 4 81
5 2 81
10 9 6
1 5 44
1 3 33
2 6 25
6 10 10
1 10 65
6 9 74
8 10 41
2 3 89
5 10 2
10 15
9 8 14
2 10 66
10 5 73
2 3 98
1 3 30
6 5 3
2 1 84
2 6 33
10 8 24
5 8 34
7 1 69
3 7 60
7 4 38
4 10 65
3 4 32

答案:

0
Not Unique!
287
432
406
326
264
220
273

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator