POJ1789解题报告

题目地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1789

此题的关键是将问题转化为最小生成树的问题。每一个编号为图的一个顶点，顶点与顶点间的编号差即为这条边的权值，题目所要的就是我们求出最小生成树来。这里我用prim算法来求最小生成树。

代码：

查看源代码

打印帮助

01	import java.io.PrintWriter;

02	import java.util.Scanner;public class Main {

03

04	public static void main(String[] args) {

05	//Scanner scn = new Scanner(System.in);

06	Scanner scn = new Scanner(Main.class.getResourceAsStream("in.dat"));

07	PrintWriter out = new PrintWriter(System.out);

08	int[][] table;

09	String[] input;

10	int n = 0;

11	while(true){

12	n = scn.nextInt();

13	if(n == 0){

14

break;

15

}

16	input = new String[n];

17	table = new int[n][n];

18	for(int i = 0; i < n; i++){

19	input[i] = scn.next();

20

}

21

//初始化数据

22	for(int i = 0; i < n; i++){

23	for(int j = 0; j < n; j++){

24	int disc = (i == j)?0:getDisc(input[i], input[j]);

25	table[i][j] = disc == 0? Integer.MAX_VALUE: Math.abs(disc);

26

}

27

}

28	//out.format("The highest possible quality is 1/%d.\n", prim(table,n));

29	out.println("The highest possible quality is 1/" + prim(table, n) + ".");

30

31

}

32	out.flush();

33

}

34	public static int prim(int[][] table,int n){

35	int[] lowcost = new int[n];

36	boolean[] s = new boolean[n];

37	int sum = 0;

38	s[0] = true;//从第一个位置开始

39	for(int i = 1; i < n; i++){

40	lowcost[i] = table[0][i];

41	s[i] = false;

42

}

43	//找到 j - s 中的最小权边

44	for(int i = 1; i < n; i++){

45	int min = Integer.MAX_VALUE;

46	int j = 1;

47	for(int k = 1; k < n; k++){

48	if((lowcost[k] < min) && (!s[k])){

49	min = lowcost[k];

50

j = k;

51

}

52

}

53	s[j] = true;//加入到j 加入到 s 集合中来

54	//sum += min;

55	for(int k = 1; k <n; k++){

56	if(table[j][k] < lowcost[k] && (!s[k])){

57	lowcost[k] = table[j][k];

58

}

59

}

60

}

61	for(int i = 0; i < n; i++){

62	sum += lowcost[i];

63

}

64	return sum;

65

}

66

/**

67	* 计算出当前行有几个元素不为a

68	* @param next

69

* @return

70

*/

71	private static int getDisc(String str1,String str2) {

72	int num = 0;

73	for(int i = 0; i < 7; i++){

74	if(str1.charAt(i) != str2.charAt(i)){

75

num++;

76

}

77

}

78	return num;

79

}

80

}

www.xiaoeblog.com