F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 3206 >> 这题解法应该是有问题的>_<
123321 @ 2016-05-25 22:15:03
[ Quote ] [ Edit ] [ Delete ] 1#
网上找了几份标程,如果将m条边反着读入(从m到1)的话就会炸。。
虽然有排序,但是如果排序完边的具体顺序不同的话答案就会不一样。。。
因为缩点的时候,可能因为求出来的mst不同,而有不同的缩点方案....
所以大概这题的做法都是不靠谱的?


具体数据:

数据1:
7 15 2
1 2 7
1 3 1
1 4 4
3 5 10
1 6 1
1 7 9
4 6 5
2 1 3
1 4 5
4 7 1
1 5 7
3 5 1
1 4 1
3 1 1
5 7 4

4 2
7 5
1 1 1 1 1 1 1

数据2:
7 15 2
1 2 7
1 3 1
1 4 4
3 5 10
1 6 1
1 7 9
4 6 5
2 1 3
1 4 5
4 7 1
1 5 7
1 4 1
3 5 1
3 1 1
5 7 4

4 2
7 5
1 1 1 1 1 1 1

两个数据只是输入有1条边的顺序不同。。然而会求出来4和6两个答案= =


求靠谱姿势QAQ
Claris @ 2016-05-25 22:44:31
[ Quote ] [ Edit ] [ Delete ] 2#
这组数据不合法,题目规定不能有重边
123321 @ 2016-05-26 13:27:03
[ Quote ] [ Edit ] [ Delete ] 3#
11 21 1
1 2 3
2 3 2
2 4 1
3 4 5
1 5 4
4 5 5
1 6 5
3 6 5
5 6 2
1 7 4
2 7 3
3 7 2
5 7 5
7 8 1
4 9 4
6 9 2
1 10 3
3 11 2
4 11 2
7 11 4
10 11 1

1 10

1 1 1 1 1 1 1 1 1 1 1



11 21 1
10 11 1
7 11 4
4 11 2
3 11 2
1 10 3
6 9 2
4 9 4
7 8 1
5 7 5
3 7 2
2 7 3
1 7 4
5 6 2
3 6 5
1 6 5
4 5 5
1 5 4
3 4 5
2 4 1
2 3 2
1 2 3

1 10

1 1 1 1 1 1 1 1 1 1 1

这两组数据就没重边了。。。
Claris @ 2016-05-26 14:51:34
[ Quote ] [ Edit ] [ Delete ] 4#
还是不合法,题目规定所有边权互不相等
123321 @ 2016-05-26 18:51:18
[ Quote ] [ Edit ] [ Delete ] 5#
woc没读题的忧伤>_<。。谢提醒QAQ
huzhaoyang @ 2018-07-24 21:13:15
[ Quote ] [ Edit ] [ Delete ] 6#
题目里不是说“注意:边权值可能相同”
[Top] [Previous Page] [Next Page]

HOME Back