2018中兴迪杰斯特拉比赛代码

注意，此程序包缺少几个对象的定义类文件，本以为无大碍 ，因为程序主要是看逻辑，定义的类换一个场景可能就失效了。但是，鉴于大家的反馈，我将在重新上传完整的代码。下载此资源的朋友也可通过加我的QQ与我交流沟通。 本资源是我参与中兴迪杰斯特拉比赛的解题代码，效果还不错，但是可惜比赛终止了。如果有相似的情景需求可以参考一下。从测试赛题来看，网格中在网格中有1000个链路需要填入，每个链路都有三个选择，而我们的目标是要使填完后网格中的最大链路利用率最低。看起来简单，但是要在一分钟内尽可能地逼近最优解（用工具测试的样例的最优解是37.08左右，这需要运行几分钟的时间），还是很有挑战的。

package com.hsy.competition2;

import java.math.BigDecimal;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;



public class Main {
	
	public static void main（String[] args） {
		// TODO Auto-generated constructor stub
		LogUtil.printLog（“Begin“）;
		String girdPath = “D:\\资料\\中兴比赛\\迪杰斯特拉\\case1\\gridtopo.txt“;
		String reqPath = “D:\\资料\\中兴比赛\\迪杰斯特拉\\case1\\request.txt“;
		String resPath = “D:\\资料\\中兴比赛\\迪杰斯特拉\\case1\\结果.txt“;
		String[] grid = FileUtil.read（girdPath null）;
		String[] req = FileUtil.read（reqPath null）;
		
	/*=============================处理Gridtopo.txt=================================== */
		
		Gridtopo topo = new Gridtopo（）;
		topo.totalNodeNum = Integer.parseInt（grid[0].split（“ “）[0]）;
		topo.totalPathNum = Integer.parseInt（grid[0].split（“ “）[1]）;
		int[][] totalBW = new int[topo.totalNodeNum][topo.totalNodeNum];
		int[][] usedBW = new int[topo.totalNodeNum][topo.totalNodeNum];
		int[][] link = new int[topo.totalPathNum][2];
	
		for（int i=1;i<=topo.totalPathNum;i++）{
			String s[] = grid[i].split（“ “）;
			int nodeA = Integer.parseInt（s[0]）;
			int nodeB = Integer.parseInt（s[1]）;
			int bandWith = Integer.parseInt（s[2]）;
			//有向图
			link[i-1][0] = nodeA;
			link[i-1][1] = nodeB;
			totalBW[nodeA][nodeB] = bandWith;		
			totalBW[nodeB][nodeA] = bandWith;
		
//			topo.Nodes.add（new Node（nodeAnodeBbandWith））;
//			topo.Nodes.add（new Node（nodeBnodeAbandWith））;
		}
		
	/*=============================处理request.txt=================================== */
		
		int totalRequestNum = Integer.parseInt（req[0].split（“ “）[0]）;
		int eachRquestPathNum = Integer.parseInt（req[0].split（“ “）[1]）;
		Requests requests = new Requests（totalRequestNumeachRquestPathNum）;
		Requests newRequests = new Requests（totalRequestNumeachRquestPathNum）;
		int index = 1;
		for（int i=0;i			
			int id = Integer.parseInt（req[index].split（“ “）[0]）;
			int bandWidth = Integer.parseInt（req[index].split（“ “）[1]）;
			
			index++;
			ArrayList> paths = new ArrayList<>（eachRquestPathNum）;
			for（int j=0;j				
				String[] strList = req[index++].split（“ “）;
				ArrayList path = new ArrayList<>（）;
				
				for（String s:strList）{
					path.add（Integer.parseInt（s））;
				}
				
				paths.add（path）;
			}
			Request request = new Request（id bandWidth paths）;
			newRequests.getRequestsList（）.add（request）;
			requests.getRequestsList（）.add（request）;
		}
		
		/*=============================分配=================================== */
			
		double score = SA.assign（requeststotalBWusedBWlink）;
		System.out.println（“最终“+score）;
		
		
		if（score > 1）{
			System.out.println（“NA“）;
			FileUtil.write（resPath new String[] { “NA“ } false）;
		}else{
	/*============================输出结果=======================================*/
			String[] result = new String[requests.getTo

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

     文件     314807  2018-04-18 09:44  迪杰斯特拉\case1\grditopoAndRequest.txt

     文件      13916  2018-03-19 10:23  迪杰斯特拉\case1\gridtopo.txt

     文件     300891  2018-03-19 10:23  迪杰斯特拉\case1\request.txt

     文件     107030  2018-04-18 09:48  迪杰斯特拉\case1\result.txt

     文件     105833  2018-08-23 11:03  迪杰斯特拉\case1\结果.txt

     文件        346  2018-04-18 10:54  迪杰斯特拉\readme.txt

     文件       3787  2018-08-23 11:03  迪杰斯特拉\代码\Main.java

     文件        220  2018-08-23 11:12  迪杰斯特拉\代码\readme.txt

     文件       6235  2018-05-08 10:21  迪杰斯特拉\代码\SA.java

     文件     105801  2018-05-07 10:43  迪杰斯特拉\代码\结果.txt

     文件     254296  2018-04-18 10:49  迪杰斯特拉\迪杰斯特拉门派赛题.pdf

     目录          0  2018-08-23 11:08  迪杰斯特拉\case1

     目录          0  2018-08-23 11:09  迪杰斯特拉\代码

     目录          0  2018-08-23 11:08  迪杰斯特拉

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

              1213162                    14