Difference between revisions of "2018 ICPC Asia Singapore Regional Contest"

From EOJ Wiki
Jump to navigation Jump to search
(Created page with "== Problem A == Solved by Kilo_5723. 00:59:24 (+) == Problem B == Solved by Xiejiadong. 00:35:08 (+) == Problem C == Solved by Weaver_zhu. 00:43:14 (+) == Problem D ==...")
 
Line 6: Line 6:
  
 
Solved by Xiejiadong. 00:35:08 (+)
 
Solved by Xiejiadong. 00:35:08 (+)
 +
 +
题意:可以在 $n$ 个点中选择一个点作为信号基站,信号的传递是跳边(间隔传递)的,求添加最小数量的边,使得消息传遍全图。
 +
 +
题解:显然如果图中有 $n$ 个联通块,我们需要用 $n-1$ 条边将他们连接起来。
 +
 +
而此时无法把信息传遍全图的情况,只剩下了,这张图是二分图的情况。显然在不同联通块之间加边并不会影响是否是二分图,直接判断即可。
  
 
== Problem C ==
 
== Problem C ==

Revision as of 06:57, 6 October 2019

Problem A

Solved by Kilo_5723. 00:59:24 (+)

Problem B

Solved by Xiejiadong. 00:35:08 (+)

题意:可以在 $n$ 个点中选择一个点作为信号基站,信号的传递是跳边(间隔传递)的,求添加最小数量的边,使得消息传遍全图。

题解:显然如果图中有 $n$ 个联通块,我们需要用 $n-1$ 条边将他们连接起来。

而此时无法把信息传遍全图的情况,只剩下了,这张图是二分图的情况。显然在不同联通块之间加边并不会影响是否是二分图,直接判断即可。

Problem C

Solved by Weaver_zhu. 00:43:14 (+)

Problem D

Solved by Kilo_5723. 04:44:16 (+11)

Problem E

Unsolved.

Problem F

Solved by Xiejiadong. 02:56:54 (+5)

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Solved by Weaver_zhu. 00:17:28 (+)

Problem K

Solved by Kilo_5723. 03:10:39 (+1)

Problem L

Solved by Kilo_5723. 00:15:15 (+)