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

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