T******7 发帖数: 1419 | 1 TopCoder problem "StrangeCountry" used in SRM 441 (Division I Level Two)
题目看下面链接
难度不小啊。做了一个小时了。哎。 | T******7 发帖数: 1419 | | m*****n 发帖数: 2152 | 3 看都看不懂,最后一个,我怎么看都是1, 为什么答案是-1? | t**r 发帖数: 3428 | 4 no. it cannot work.
it's like
0 --- 1 --- 2 --- 3
4 -- 5
there is no circle for one set. Cannot make them connected by doing
operation mentioned above.
So no solution, return -1
【在 m*****n 的大作中提到】 : 看都看不懂,最后一个,我怎么看都是1, 为什么答案是-1?
| m*****n 发帖数: 2152 | 5 Thanks. 刚才题意理解错了,改了一下code,结果就对了. 这道题应该不难吧.包括改错,
一共就写了30分钟.
【在 t**r 的大作中提到】 : no. it cannot work. : it's like : 0 --- 1 --- 2 --- 3 : 4 -- 5 : there is no circle for one set. Cannot make them connected by doing : operation mentioned above. : So no solution, return -1
| t**r 发帖数: 3428 | 6 can you share your code?
错,
【在 m*****n 的大作中提到】 : Thanks. 刚才题意理解错了,改了一下code,结果就对了. 这道题应该不难吧.包括改错, : 一共就写了30分钟.
| m*****n 发帖数: 2152 | 7 刚才又看了一下,这个code 有bug,就删掉不误导大家了. | r****7 发帖数: 2282 | 8 觉得这个题没啥意思,operation的定义很confuse,想了十几分钟才明白他的
operation是啥。然后G的上限就50个,可以用*fs不停的算,数边就可以了。
【在 T******7 的大作中提到】 : TopCoder problem "StrangeCountry" used in SRM 441 (Division I Level Two) : 题目看下面链接 : 难度不小啊。做了一个小时了。哎。
| b****h 发帖数: 163 | 9 这道题可以直接计算图里有几个联通子图,同时计算每个联通子图中环的数目,如果总
共环的数目小于子图数目-1,就返回-1,否则返回联通子图数目-1
这样应该可以吧? | H******7 发帖数: 1728 | 10 Operation没有问题啊
四个点 destroy 两条边 画两条连接四点的不同新边
★ 发自iPhone App: ChineseWeb 8.7
【在 r****7 的大作中提到】 : 觉得这个题没啥意思,operation的定义很confuse,想了十几分钟才明白他的 : operation是啥。然后G的上限就50个,可以用*fs不停的算,数边就可以了。
| | | r****7 发帖数: 2282 | 11 不是总的环的数目,而是大于生成树的边的数目。
【在 b****h 的大作中提到】 : 这道题可以直接计算图里有几个联通子图,同时计算每个联通子图中环的数目,如果总 : 共环的数目小于子图数目-1,就返回-1,否则返回联通子图数目-1 : 这样应该可以吧?
| b****h 发帖数: 163 | 12 这个和生成树中边的数目有什么关系?一个生成树中可以有很多条边,但不代表它能把
2个子图连起来啊,比如一个子图是一颗树,另外一个子图2个节点连着,这2个子图肯
定连不上啊
【在 r****7 的大作中提到】 : 不是总的环的数目,而是大于生成树的边的数目。
| t**r 发帖数: 3428 | 13 贴个答案
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
| b****h 发帖数: 163 | 14 这思路和我上面那个帖子一样~~
【在 t**r 的大作中提到】 : 贴个答案 : #include : #include : #include : #include : #include : #include : #include : #include : #include
| t**r 发帖数: 3428 | 15 "这道题可以直接计算图里有几个联通子图,同时计算每个联通子图中环的数目,如果总
共环的数目小于子图数目-1,就返回-1,否则返回联通子图数目-1
这样应该可以吧?"
Yeah. This is the solution. Good explanation man. |
|