Difference between revisions of "2018 ICPC Asia Singapore Regional Contest"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) (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 ==...") |
Xiejiadong (talk | contribs) |
||
| 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 (+)