骆驼商队问题——2001年11期编程擂台题解

• 作者: 胡海星
• 来源期刊: Internet信息世界
• 学科: 工学
• 关键词: 程序设计 骆驼商队问题 编程擂台题解
• 年，卷（期）: cxy_2002,（1）
• 页码范围: 100-101
• 页数: 2页
• 分类号: TP311.1

摘要

<正> 问题描述见2001年第11期杂志。问题分析去除题目中的实际背景,本题可以用数学语言描述成:在一个带权无向图G中找出一生成子图G’,使得G’的每个顶点出度不超过1,并且G’所有边的权值之和最大。首先,如果这个图是不连通的,那么它的各个连通分量之间是没有任何联系的。对这些连通分量中的问题可以分别独立