2013年 中兴捧月杯 程序设计第二题复赛

2013年 中兴捧月杯 程序设计（第二题）复赛 未能进入决赛。。。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;


public class Dnf {

	HashMap minCost = new HashMap（）;
	/**
	 * 源顶点
	 */
	int source;
	/**
	 * 目的顶点
	 */
	int destination;
	/**
	 * 顶点约束
	 */	
	int limitVer[];
	/**
	 * 存储着网络顶点以及各顶点间图结构的Map类用于寻找无中间顶点约束的最短路劲查找
	 */
	Map map = null;
	/**
	 * 当前找到最优路径
	 */
	List bestWay = new ArrayList（）;
	/**
	 *  当前找到最优解路径的长度
	 */
	int bestRange = Integer.MAX_VALUE;
	/**
	 * 解空间树的最大层数（从0开始计算）
	 */
	int end_floor = 0;
	
	/**
	 * 记录路径中已经经过的约束顶点
	 */
	List usedVer = new ArrayList（50）;
	
	/**
	 * 解空间树。如tree[i]表示解空间树第i层路径的顶点列表
	 */
	List[] tree = null;
	
	/**
	 * 用于计算解空间树的遍历量...
	 * 解空间树第二层已遍历结点
	 */
	int fz = 0;
	/**
	 * 用于计算解空间树的遍历量...
	 * 解空间树第二层总结点数
	 */
	double fm;
	
	/**
     * 构造函数
     * 设置一些常用的数据，以减小系统开支
     * @param source	源顶点
     * @param destination	 目的顶点
     * @param limitPoints   用户输入的必须经过的顶点（包含源顶点和目的顶点）
     * @param map		存储着网络顶点以及各顶点间图结构的Map类
     * @return  void
     */
	public Dnf（int sourceint destinationint[] limitPointsMap map） {
		this.setCommonData（source destination limitPoints map）;
	}
	
	
	/**
     * 设置一些常用的数据，以减小系统开支
     * @param source	源顶点
     * @param destination	 目的顶点
     * @param limitPoints   用户输入的必须经过的顶点（包含源顶点和目的顶点）
     * @param map		存储着网络顶点以及各顶点间图结构的Map类
     * @return  void
     */
	private void setCommonData（int sourceint destinationint[] limitPointsMap map）{
		this.source = source;
		this.destination = destination;
		this.limitVer = limitPoints;
		this.map = map;
		this.end_floor = limitVer.length-1;
		
		for（int i = 0;i			int s = limitVer[i];
			map.setTreeFromSource（s）;
			for（int j = i+1;j				if（i==j）
					continue;
				int d = limitVer[j];
				minCost.put（s*10000+d map.tree[d].range）;
				minCost.put（s+d*10000 map.tree[d].range）;
			}
			minCost.put（destination*10000+destination 0）;
		}
	}
	
	
	/**
	 * 返回最优解的字符串表现形式
	 * @return 返回最优解的字符串表现形式
	 */
	public String getWay（）{
		
		List r = searchWay（）;
		
		if（r!=null && r.size（）>0）{
			String s = ““;
			for（Integer i : r）{
				s = s+i+““;
			}
			return s.substring（0 s.length（）-1）;
		}
		else
			return “NOT FOUND!“;
	}


	/**
     * 动态寻找最优解
     * @return  最优路径的顶点列表
     */
	@SuppressWarnings（“unchecked“）
	private List searchWay（） {
		
		usedVer.add（source）;
		tree = new ArrayList[limitVer.length-1];
		fm = limitVer.length*（limitVer.length-1）;
		
		map.resetUsedVer（）;
		branch（source00）;
		
		return bestWay;
	}
	
	
	/**
     * 分支限界算法核心函数动态更新最优解 bestWay & bestRange 
     * @param start_ver		开始顶点点，当前路径的末尾顶点，下一段路径的开始顶点
     * @param floor		当前开始顶点在解空间树中的层数（从0开始）
     * @param range		当前开始顶点在约束条件下距离源开始顶点的距离
     * @return  void
     */
	private void branch（int start_verint floorint range） {
		if（

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        183  2013-08-03 21:58  复赛\Read me.txt

     文件       6303  2013-08-03 12:54  复赛\source code\Dnf.java

     文件       2824  2013-08-03 12:08  复赛\source code\Main.java

     文件       4866  2013-08-04 09:15  复赛\source code\Map.java

     文件         55  2013-08-04 09:25  复赛\ZTE.bat

     文件      15322  2013-08-04 09:15  复赛\ZTE.jar

     文件      30208  2013-08-04 09:24  复赛\说明文档.doc

     目录          0  2013-08-04 09:19  复赛\source code

     目录          0  2013-08-04 09:28  复赛

----------- ---------  ---------- -----  ----

                59761                    9