C——Network Saboteur （POJ2531）
2021-06-12 14:04
阅读：450
90解题思路：
首先这个题目的题意就比较难理解。题目大意：有n个点，每两个点之间都有一段距离，现在要把这些点分为两部分，使得一个部分的点到另一个部分所有的点的距离和最大。（学过离散的就知道这是一个完全图）比如题中的例子：就是一个K3图（3个顶点的完全图，一个三角形），设顶点为A，B，C.由题意可知：A到B的距离为30，B到C为40，C到A为50.当把A放一边，B，C放一边时，总距离为：A到B的距离（30）+A到C的距离（50）=80.当把C放一边，A，B一边时，总距离为AC+BC=90，另一种为30+40=70.所以最大的距离和为90.
看懂题目的可能都知道要用枚举来找最大距离和，但是怎么枚举呢？用for循环？肯定行不通的。这里就用”二进制枚举“来枚举所有情况并找到最大值。二进制枚举（非递归）：
用数组的值为0或1来把所有的点来分为两部分。
文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：C——Network Saboteur （POJ2531）
文章链接：http://soscw.com/index.php/essay/93892.html
文章标题：C——Network Saboteur （POJ2531）
文章链接：http://soscw.com/index.php/essay/93892.html
评论
亲，登录后才可以留言！