2013
11-09

# POJ 1251 Jungle Roads [解题报告] Java

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));
}
}
}

import java.io.BufferedInputStream;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
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;
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();
j++;
}
}
Iterator< Edge> ite = l.iterator();
Integer sum = 0;
while (ite.hasNext()) {
Edge e = ite.next();
sum = sum + e.getValue();
}
System.out.println(sum);
}
}

Collections.sort(graph);
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) {
vertexes.put(e.getVertex1(), tree);
vertexes.put(e.getVertex2(), tree);
} else {
if (!vertexes.containsKey(e.getVertex1()) && vertexes.containsKey(e.getVertex2())) {
vertexes.put(e.getVertex1(), vertexes.get(e.getVertex2()));

} else if (vertexes.containsKey(e.getVertex1()) && !vertexes.containsKey(e.getVertex2())) {
vertexes.put(e.getVertex2(), vertexes.get(e.getVertex1()));
} else if (!vertexes.containsKey(e.getVertex1()) && !vertexes.containsKey(e.getVertex2())) {
tree++;
vertexes.put(e.getVertex1(), tree);
vertexes.put(e.getVertex2(), tree);
} else if (vertexes.get(e.getVertex1()) != vertexes.get(e.getVertex2())) {
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();
}
}