package algorithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

/*
現在有一個國家，有n個城市和n-1條邊，每條邊長為1，這個國家每個城市都可以直接或者間接到底另一個城市，國家的首都為1號，現在
國王決定修一條長度為1的道路，這條道路將連接首都到另一個城市，由于修建道理成本很大，國王聯系你，希望找到這邊邊連接的另一個城市，
使首都到所有城市的最短距離之和最小。

輸入：
第一行正整數n
后面n-1行，每行2個數u,v，表示u到v有一條邊。數據保證給出的圖是一棵樹。
輸出：
一個整數，為首都到每個城市的總長度之和

輸入：
6
1 2
2 3
3 4
3 5
3 6
輸出：
8
此時為
d00+d01+d02+d03+d04+d05=0+1+1+2+2+2=8

輸入9：
1 2
2 3
3 4
4 5
4 6
5 7
5 8
5 9
輸出：15 ? 在城市5和首都修路，距離最小

?
?*/

public class KingGraphCaravan {

? ? private ArrayList vertexList;//存儲點的鏈表
? ? private static int[][] edges;//鄰接矩陣，用來存儲邊
? ? private int numOfEdges;//邊的數目
? ? static int maxResult=0;
? ??
? ? public KingGraphCaravan(int n) {
? ? ? ? //初始化矩陣，一維數組，和邊的數目
? ? ? ? edges=new int[n][n]; ?//邊初始化均為0
? ? ? ? vertexList=new ArrayList(n); ?//n個邊
? ? ? ? numOfEdges=0;
? ? }
? //得到結點的個數
? ? public int getNumOfVertex() {
? ? ? ? return vertexList.size();
? ? }

? ? //得到邊的數目
? ? public int getNumOfEdges() {
? ? ? ? return numOfEdges;
? ? }

? ? //返回結點i的數據
? ? public Object getValueByIndex(int i) {
? ? ? ? return vertexList.get(i);
? ? }
? ??
? ? //返回v1,v2的權值
? ? public int getWeight(int v1,int v2) {
? ? ? ? return edges[v1][v2];
? ? }

? ? //插入結點
? ? public void insertVertex(Object vertex) {
? ? ? ? vertexList.add(vertexList.size(),vertex); //add(index,object) 插入對象
? ? }

? ? //插入邊
? ? public void insertEdge(int v1,int v2,int weight) {
? ? ? ? edges[v1][v2]=weight;
? ? ? ? numOfEdges++;
? ? }
? ??
? ? //刪除邊
? ? public void deleteEdge(int v1,int v2) {
? ? ? ? edges[v1][v2]=0;
? ? ? ? numOfEdges--;
? ? }
? ??
? ? //得到第一個鄰接結點的下標
? ? public int getFirstNeighbor(int index) {
? ? ? ? for(int j=0;j<vertexList.size();j++) {
? ? ? ? ? ? if (edges[index][j]>0) {
? ? ? ? ? ? ? ? return j;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return -1;
? ? }

? ? //根據前一個鄰接結點的下標來取得下一個鄰接結點
? ? public int getNextNeighbor(int v1,int v2) {
? ? ? ? for (int j=v2+1;j<vertexList.size();j++) {
? ? ? ? ? ? if (edges[v1][j]>0) {
? ? ? ? ? ? ? ? return j;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return -1;
? ? }

??
? ??
? ? //得到第一個鄰接結點的下標
? ? public void getMyFirstNeighbor(int index,boolean[] isVisited ,LinkedList queue
? ? ?? ??? ?,Map<Integer,Integer> mapValue) {
? ? ? ? for(int j=0;j<vertexList.size();j++) {
? ? ? ? ?? ?
? ? ? ? ? ? if (edges[index][j]>0&&isVisited[j]==false) {//未被訪問
? ? ? ? ? ? ?? ?
? ? ? ? ? ? ?? ?queue.add(j); //添加
? ? ? ? ? ? ?? ?
? ? ? ? ? ? ?? ?isVisited[j]=true;
? ? ? ? ? ? ?? ?
? ? ? ? ? ? ?? ?mapValue.put(j,mapValue.get(index)+1);
? ? ? ? ? ??
? ? ? ? ? ? ? ?
? ? ? ? ? ? }
? ? ? ? }
? ? ??
? ? }

? ?public void solution(LinkedList queue,boolean[] isVisited,Map<Integer,Integer> mapValue) {
? ? ? ? ?? ?
?? ? ?
?? ? ? ?if(!queue.isEmpty()){//不為空
?? ? ? ??? ?int w=(int) queue.remove();//獲取值
?? ? ? ??? ?getMyFirstNeighbor(w,isVisited,queue,mapValue);
?? ? ? ??? ?solution(queue,isVisited,mapValue);
?? ? ? ?}
? ?
? ? }
?
??
? ?public static int distanceSum(Map<Integer,Integer> mapValue){
?? ? ? int sum=0;
?? ??? ?System.out.println("首都到各城市的距離如下：");
?? ??? ?for(int hh:mapValue.keySet()){
?? ??? ??? ?if(hh!=0){
?? ??? ??? ?int tmp=mapValue.get(hh);
?? ??? ??? ?sum+=tmp;
?? ??? ??? ?}
?? ??? ?}
?? ??? ?return sum;
? ?}
? ??
?? ?public static void main(String[] args) {

?? ??? ?
?? ??? ?Scanner sc=new Scanner(System.in);
?? ??? ?String hh=sc.nextLine();
?? ?
?? ??? ?int n=Integer.parseInt(hh); //表示節點
?? ??? ?//String labels[]={"1a","2b","c3","4d","5e"};//結點的標識
?? ??? ?KingGraphCaravan gc=new KingGraphCaravan(n);
?? ??? ?
?? ??? ?for(int i=0;i<n;i++){
?? ??? ??? ? ?// System.out.print(" ?"+labels[i]);
?? ??? ??? ? ? gc.insertVertex(i);
?? ??? ??? ?}
?? ??? ?
?? ??? ?for(int i=0;i<n-1;i++){
?? ??? ??? ?String t=sc.nextLine();
?? ??? ??? ?String[] h1=t.split(" ");
?? ??? ??? ?int v1=Integer.parseInt(h1[0]);
?? ??? ??? ?int v2=Integer.parseInt(h1[1]);
?? ??? ??? ?
?? ??? ??? ?gc.insertEdge(v1-1,v2-1, 1);
?? ??? ??? ?gc.insertEdge(v2-1,v1-1, 1);
?? ??? ?}
?? ??? ?
?? ??? ?
?? ?
?? ?
?? ??? ?
?? ??? ?int minSum=Integer.MAX_VALUE;
?? ??? ?int ii=0;
?? ??? ?boolean flag=true;
?? ??? ?//添加邊
?? ??? ?for(int i=1;i<n;i++){
?? ??? ??? ?//if(i!=2)
?? ??? ??? ??? ?//continue;
?? ??? ??? ?flag=true; //默認需要添加
?? ??? ??? ?if(edges[0][i]!=0){ //該邊已經存在，無需添加
?? ??? ??? ??? ?flag=false;
?? ??? ??? ?}
?? ??? ??? ?if(flag){
?? ??? ??? ??? ?gc.insertEdge(0,i, 1);
?? ??? ??? ??? ?gc.insertEdge(i,0, 1);
?? ??? ??? ?}
?? ??? ??? ?
?? ??? ?
?? ??? ?
?? ??? ??? ?Map<Integer,Integer> mapValue=new HashMap<Integer,Integer>(); //存儲到首都的距離
?? ??? ?
?? ??? ??? ?boolean[] isVisited=new boolean[n]; //默認false
?? ??? ??? ?
?? ??? ??? ?LinkedList queue=new LinkedList(); //隊列
?? ??? ??? ?queue.add(0);
?? ??? ??? ?mapValue.put(0,0); //當前節點
?? ? ? ??? ?isVisited[0]=true;
?? ??? ??? ?
?? ??? ??? ?gc.solution(queue,isVisited,mapValue);
?? ??? ??? ?
?? ??? ??? ?
?? ??? ??? ?System.out.println("首都到各城市的距離如下：");
?? ??? ??? ?for(int hh1:mapValue.keySet()){
?? ??? ??? ??? ?System.out.println(hh1+"="+mapValue.get(hh1));
?? ??? ??? ?}
?? ??? ??? ?
?? ??? ??? ?for(int k=0;k<n;k++){
?? ??? ??? ??? ?System.out.println();
?? ??? ??? ??? ?for(int k1=0;k1<n;k1++){
?? ??? ??? ??? ??? ?System.out.print(" "+edges[k][k1]);
?? ??? ??? ??? ?}
?? ??? ??? ??? ?System.out.println();
?? ??? ??? ?}
?? ??? ??? ?
?? ??? ??? ?
?? ??? ??? ?int sum=distanceSum(mapValue);
?? ??? ??? ?
?? ??? ??? ?System.out.println("此時到各城市的距離為:"+sum+" ?"+i);
?? ??? ??? ?
?? ??? ??? ?if(minSum>sum){
?? ??? ??? ??? ?minSum=sum;
?? ??? ??? ??? ?ii=i;
?? ??? ??? ?}
?? ??? ??? ?
?? ??? ??? ?//刪除其他邊
?? ??? ??? ?if(flag){
?? ??? ??? ??? ?gc.deleteEdge(0,i);
?? ??? ??? ??? ?gc.deleteEdge(i,0);
?? ??? ??? ?}
?? ??? ??? ?
?? ??? ??? ?
?? ??? ?}
?? ??? ?
?? ??? ?
?? ??? ?System.out.println("城市為(首都為0，對應輸入為0+1=1)：添加的公路為從首都0到城市"+ii+"，最小距離為："+minSum);
?? ??? ?System.out.println("名稱為首都1到城市"+(ii+1)+" ,修完后最小距離為"+minSum);
?? ??? ?
?? ??? ?
?? ?}

}
?

總結

以上是生活随笔為你收集整理的一国之主图的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。