首页 > 数据结构 > Hash表 > POJ 1251 Jungle Roads [解题报告] Java
2013
11-09

POJ 1251 Jungle Roads [解题报告] Java

Jungle Roads

问题描述 :



The Head Elder of the tropical island of Lagrishan has a problem. A burst of foreign aid money was spent on extra roads between villages some years ago. But the jungle overtakes roads relentlessly, so the large road network is too expensive to maintain. The Council of Elders must choose to stop maintaining some roads. The map above on the left shows all the roads in use now and the cost in aacms per month to maintain them. Of course there needs to be some way to get between all the villages on maintained roads, even if the route is not as short as before. The Chief Elder would like to tell the Council of Elders what would be the smallest amount they could spend in aacms per month to maintain roads that would connect all the villages. The villages are labeled A through I in the maps above. The map on the right shows the roads that could be maintained most cheaply, for 216 aacms per month. Your task is to write a program that will solve such problems.

输入:

The input consists of one to 100 data sets, followed by a final line containing only 0. Each data set starts with a line containing only a number n, which is the number of villages, 1 < n < 27, and the villages are labeled with the first n letters of the alphabet, capitalized. Each data set is completed with n-1 lines that start with village labels in alphabetical order. There is no line for the last village. Each line for a village starts with the village label followed by a number, k, of roads from this village to villages with labels later in the alphabet. If k is greater than 0, the line continues with data for each of the k roads. The data for each road is the village label for the other end of the road followed by the monthly maintenance cost in aacms for the road. Maintenance costs will be positive integers less than 100. All data fields in the row are separated by single blanks. The road network will always allow travel between all the villages. The network will never have more than 75 roads. No village will have more than 15 roads going to other villages (before or after in the alphabet). In the sample input below, the first data set goes with the map above.

输出:

The output is one integer per line for each data set: the minimum cost in aacms per month to maintain a road system that connect all the villages. Caution: A brute force solution that examines every possible set of roads will not finish within the one minute time limit.

样例输入:

9
A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35
3
A 2 B 10 C 40
B 1 C 20
0

样例输出:

216
30

解题代码:

方法一:(Prim算法)
import java.util.Scanner;
public class Main {
 
  static int MAXCOST=Integer.MAX_VALUE;
 
 static int Prim(int graph[][], int n){
   /* lowcost[i]记录以i为终点的边的最小权值,当lowcost[i]=0时表示终点i加入生成树 */
   int lowcost[]=new int[n+1];
 
   /* mst[i]记录对应lowcost[i]的起点,当mst[i]=0时表示起点i加入生成树 */
   int mst[]=new int[n+1];
 
   int min, minid, sum = 0;
 
   /* 默认选择1号节点加入生成树,从2号节点开始初始化 */
    for (int i = 2; i <= n; i++){
	/* 最短距离初始化为其他节点到1号节点的距离 */
	lowcost[i] = graph[1][i];
 
	/* 标记所有节点的起点皆为默认的1号节点 */
	mst[i] = 1;
     }
 
    /* 标记1号节点加入生成树 */
    mst[1] = 0;
 
    /* n个节点至少需要n-1条边构成最小生成树 */
    for (int i = 2; i <= n; i++){
	min = MAXCOST;
	minid = 0;
 
       /* 找满足条件的最小权值边的节点minid */
       for (int j = 2; j <= n; j++){
	  /* 边权值较小且不在生成树中 */
	  if (lowcost[j] < min && lowcost[j] != 0){
	     min = lowcost[j];
	     minid = j;
	  }
       }
     
       /* 输出生成树边的信息:起点,终点,权值 */
	//System.out.printf("%c - %c : %d\n", mst[minid] + 'A' - 1, minid + 'A' - 1, min);
 
       /* 累加权值 */
       sum += min;
 
       /* 标记节点minid加入生成树 */
       lowcost[minid] = 0;
 
       /* 更新当前节点minid到其他节点的权值 */
       for (int j = 2; j <= n; j++){
         /* 发现更小的权值 */
	  if (graph[minid][j] < lowcost[j]){
	      /* 更新权值信息 */
	      lowcost[j] = graph[minid][j];
 
	      /* 更新最小权值边的起点 */
	      mst[j] = minid;
	   }
       }
     }
     /* 返回最小权值和 */
	return sum;
   }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    while (sc.hasNext()) {   
       int n = sc.nextInt();   
       if (n == 0) {   
          break;   
        }   
       int graph[][]=new int[n+1][n+1];

      /* 初始化图,所有节点间距离为无穷大 */
       for (int i = 1; i <= n; i++){
	  for (int j = 1; j <= n; j++){
		graph[i][j] = MAXCOST;
	   }
       }
               
        for (int i = 1; i <=n-1; i++) {   
          char  chx = sc.next().charAt(0);
          int x = chx - 'A' + 1;
          int m = sc.nextInt();   
          int j = 0;   
          while (j < m) {   
              char chy= sc.next().charAt(0);  
              int y = chy - 'A' + 1;
              int cost = sc.nextInt();   
              graph[x][y] = cost;
	       graph[y][x] = cost;
              j++;   
          }   
        }   

        System.out.println(Prim(graph, n));
      }
   }
}
		
方法二:Kruskal算法
		
import java.io.BufferedInputStream;   
import java.util.Collections;   
import java.util.HashMap;   
import java.util.Iterator;   
import java.util.LinkedList;   
import java.util.Map.Entry;   
import java.util.Scanner;   
  
 
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scanner = new Scanner(new BufferedInputStream(System.in));   
        while (scanner.hasNext()) {   
            int n = scanner.nextInt();   
            if (n == 0) {   
                break;   
            }   
            String a;   
            LinkedList< Edge> graph = new LinkedList();   
            for (int i = 0; i < n - 1; i++) {   
                a = scanner.next("[A-Z]");   
                int m = scanner.nextInt();   
                int j = 0;   
                while (j < m) {   
                    String b = scanner.next("[A-Z]");   
                    int value = scanner.nextInt();   
                    graph.add(new Edge(a, b, value));   
                    j++;   
                }   
            }   
            LinkedList< Edge> l = Kruskal(graph);   
            Iterator< Edge> ite = l.iterator();   
            Integer sum = 0;   
            while (ite.hasNext()) {   
                Edge e = ite.next();   
                sum = sum + e.getValue();   
            }   
            System.out.println(sum);   
        }   
    }   
  
    static LinkedList< Edge> Kruskal(LinkedList graph) {   
        Collections.sort(graph);   
        LinkedList< Edge> g = new LinkedList();   
        HashMap< String, Integer> vertexes = new HashMap< String, Integer>();   
        Iterator< Edge> it = graph.iterator();   
        Integer tree = 0;   
        while (it.hasNext()) {   
            Edge e = it.next();   
            if (g.size() == 0) {   
                g.add(e);   
                vertexes.put(e.getVertex1(), tree);   
                vertexes.put(e.getVertex2(), tree);   
            } else {   
                if (!vertexes.containsKey(e.getVertex1()) && vertexes.containsKey(e.getVertex2())) {   
                    g.add(e);   
                    vertexes.put(e.getVertex1(), vertexes.get(e.getVertex2()));   
  
                } else if (vertexes.containsKey(e.getVertex1()) && !vertexes.containsKey(e.getVertex2())) {   
                    g.add(e);   
                    vertexes.put(e.getVertex2(), vertexes.get(e.getVertex1()));   
                } else if (!vertexes.containsKey(e.getVertex1()) && !vertexes.containsKey(e.getVertex2())) {   
                    g.add(e);   
                    tree++;   
                    vertexes.put(e.getVertex1(), tree);   
                    vertexes.put(e.getVertex2(), tree);   
                } else if (vertexes.get(e.getVertex1()) != vertexes.get(e.getVertex2())) {   
                    g.add(e);   
                    vertexes = MergeTwoTrees(vertexes, e.getVertex1(), e.getVertex2());   
                }   
            }   
        }   
        return g;   
    }   
  
    static HashMap< String, Integer> MergeTwoTrees(HashMap< String, Integer> vertexes, String v1, String v2) {   
        HashMap< String, Integer> hm = new HashMap< String, Integer>();   
        Integer a = vertexes.get(v1);   
        Integer b = vertexes.get(v2);   
        Iterator it = vertexes.entrySet().iterator();   
        while (it.hasNext()) {   
            Entry entry = (Entry) it.next();   
            String key = (String) entry.getKey();   
            Integer value = (Integer) entry.getValue();   
            if (b == value) {   
                value = a;   
            }   
            hm.put(key, value);   
        }   
        return hm;   
    }   
}   
  
class Edge implements Comparable {   
  
    private String vertex1;   
    private String vertex2;   
    private Integer value;   
  
    public Edge(String vertex1, String vertex2, Integer value) {   
        this.vertex1 = vertex1;   
        this.vertex2 = vertex2;   
        this.value = value;   
    }   
  
    public int getValue() {   
        return value;   
    }   
  
    public void setValue(int value) {   
        this.value = value;   
    }   
  
    public String getVertex1() {   
        return vertex1;   
    }   
  
    public void setVertex1(String vertex1) {   
        this.vertex1 = vertex1;   
    }   
  
    public String getVertex2() {   
        return vertex2;   
    }   
  
    public void setVertex2(String vertex2) {   
        this.vertex2 = vertex2;   
    }   
  
    public int compareTo(Object o) {   
        Edge e = (Edge) o;   
        return this.value - e.getValue();   
    }   
}