紧急医疗救护站设置问题 最短路径 覆盖城镇

假设有一个县医疗救护中心有一些救护车为全县服务，如果这些救护车平时都放置在县城，那么当偏远地区病人需要紧急运往医院时就不能及时到达现场。所以需要在各乡镇及村庄建立紧急医疗救护站，分散放置这些救护车，以便尽可能使得场全县任何地方有病人时可以在20分钟内到达现。假设一个救护站配备一辆救护车，司机随时值班，需要时即可使用。 1. 设救护站可以设在各乡镇及村庄，那么最少需要设置多少救护站可以使得所有人口位于救护车20分钟车程能够覆盖的范围内？给出各救护站位置。如果救护站只能位于乡（镇）所在地，结果怎样？ 2. 假设共有10辆救护车，怎样设置救护站的位置可以使得尽可能多的人口位于救护车20分钟车程能够覆盖的范围内？能覆盖所有人口吗？如果不能，多少人不能被覆盖？如果救护车的数量为7辆，再次回答上述问题。

package xiong;

import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.List;

/**
 * 类详细描述:专门打印最近距离的矩阵，和0-1矩阵
 * 
 * @ClassName TestMainIO
 * @author 刘群
 * @date 2015-12-30 下午4:28:21
 */
public class Array_Floyd {

	/** 
	 * @Fields Length : 数组长度
	 */ 
	static int Length = 53;
	
	/** 
	 * @Fields Distance : 判定范围，两城镇之间，大于20即为不覆盖，小于则覆盖
	 */ 
	static int Distance = 20;
	
	/** 
	 * @Fields A : 0-1矩阵，可达为1，不可达为0
	 */ 
	static int[][] A = new int[Length][Length];
	
	/** 
	 * @Fields point : 类似0-1矩阵，只是值是truefalse
	 */ 
	static boolean[][] point = new boolean[Length][Length];
	
	/** 
	 * @Fields nums : 记录每个点可以到达多少个点
	 */ 
	public static int[] nums = new int[Length];
	
	/** 
	 * @Fields list : 记录每一条路径的时候所用的
	 */ 
	public static List list = new ArrayList（）;

	
	/** 
	 * 方法简述：main方法
	 * @param args 
	 */
	public static void main（String[] args） {
		
		Data data = new Data（）;
		data.initGrp（）;
		
		//从data类中获取数据
		double[][] G = data.getGrp（）;
		double[][] Dis = floyd（G Length）;
		//printG（G Length）;
//		printG（Dis Length）;
//		System.out.println（“============================“）;
//		initA（Dis Length）;
		initA（G）;
		printG（A Length）;
	}

	public static int[][] initA（double[][] G） {
	char ch = ‘A‘;
	for （int i = 0; i < G.length; i++） {
		
		for （int j = 0; j < G[i].length; j++） {
			if （G[i][j] != 1000） {
				A[i][j] = 1;
			}else {
				A[i][j] = 0;
				//System.out.println（“（“+i+““+j+“）“）;
			}
		}
	}
	return A;
	}
	
	
	/** 
	 * 方法简述：生成0-1矩阵
	 * @param G 最近距离的矩阵
	 * @param n 矩阵的宽度
	 */
	public static int[][] initA（double[][] G int n） {

		for （int i = 0; i < n; i++） {
			for （int j = 0; j < n; j++） {
				if （G[i][j] > Distance） {
					A[i][j] = 0;
				} else {

					A[i][j] = 1;
				}
			}
		}
		return A;
	}

	/** 
	 * 方法简述： 初始化nums数组
	 */
	public static void initNums（） {
		for （int i = 0; i < nums.length; i++） {
			nums[i] = -1;
		}

	}

	/** 
	 * 方法简述：打印数组，调用可以在控制台输出最近距离的那个矩阵
	 * @param G 数组
	 * @param n 数组长度
	 */
	public static void printG（double[][] G int n） {
		DecimalFormat df = new DecimalFormat（“#.00“）;
		
		for （int i = 0; i < n; i++） {
			System.out.print（i + “:“）;
			for （int j = 0; j < n; j++） {
				System.out.print（j+“:“+df.format（G[i][j]） + “ “）;
				if （j == n-1） {
					//System.out.print（“\nG[i][j]“+52 + “\n“）;
				}
			}
			System.out.println（）;
		}
	}

	/** 
	 * 方法简述：打印整型的那个数组，用于打印0-1矩阵
	 * @param G
	 * @param n 
	 */
	public static void printG（int[][] G int n） {
		char ch = ‘A‘;
		int count = 1;
		for （int i = 0; i < n; i++） {
			int k = 0;
			if （i<18） {
				System.out.print（（ch++）+“:“）;
			}else {
				System.out.print（（count++）+“:“）;
			}
			for （int j = 0; j < n; j++） {
				System.out.print（G[i][j] + ““）;
				if （G[i][j] == 1） {
					k++;
				}
			}

			System.out.print（“:“+（k））;
			System.out.println（）;
		}
	}

	/** 
	 * 方法简述：最短路径的生成

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2016-01-05 14:32  xiong\
     文件       56589  2016-01-03 22:46  xiong\1.txt
     文件         575  2016-01-03 23:43  xiong\2.txt
     文件         284  2016-01-05 10:06  xiong\4.txt
     文件        3967  2016-01-03 23:30  xiong\Array_Floyd.java
     文件        4711  2016-01-03 21:08  xiong\CopyOfArray_Floyd.java
     文件       40523  2016-01-03 23:36  xiong\Data.java
     文件        5151  2016-01-04 22:44  xiong\Exercise_1.java
     文件        6733  2016-01-03 23:37  xiong\Exercise_2.java
     文件        5723  2016-01-03 16:32  xiong\Exercise_3.java
     文件        5151  2016-01-05 10:00  xiong\Exercise_4.java
     文件     1331874  2016-01-05 12:24  xiong\紧急医疗救护站设置问题的题目.zip