codeforces 330 B. Road Construction (图论基础)

题目链接
题意:n个点,m(m<n/2)条不能走的边,问最少连多少条边,使得任何两个点之间的距离最多为2. 输出最少的边数和连接的哪些边。
思路: 数据范围很关键。数据范围很关键。数据范围很关键。

因为m<n/2,每条禁止的边最多禁止两个点,所以禁止的点数<n..那么至少有一个点是和可以和其他所有点相连的。。于是把其他所有点和该点相连即可。

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz