Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
用prim的次最小生成树WA的看过来,绝对受益!!!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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator