# Poj Solution 1789

```http://poj.org/problem?id=1789

import java.io.PrintWriter;
import java.util.Scanner;public class Main {

public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
//Scanner scn = new Scanner(Main.class.getResourceAsStream("in.dat"));
PrintWriter out = new PrintWriter(System.out);
int[][] table;
String[] input;
int n = 0;
while(true){
n = scn.nextInt();
if(n == 0){
break;
}
input = new String[n];
table = new int[n][n];
for(int i = 0; i < n; i++){
input[i] = scn.next();
}
//��ʼ�����
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
int disc = (i == j)?0:getDisc(input[i], input[j]);
table[i][j] = disc == 0? Integer.MAX_VALUE: Math.abs(disc);
}
}
//out.format("The highest possible quality is 1/%d.n", prim(table,n));
out.println("The highest possible quality is 1/" + prim(table, n) + ".");

}
out.flush();
}
public static int prim(int[][] table,int n){
int[] lowcost = new int[n];
boolean[] s = new boolean[n];
int sum = 0;
s[0] = true;//�ӵ�һ��λ�ÿ�ʼ
for(int i = 1; i < n; i++){
lowcost[i] = table[0][i];
s[i] = false;
}
//�ҵ� j - s �е���СȨ��
for(int i = 1; i < n; i++){
int min = Integer.MAX_VALUE;
int j = 1;
for(int k = 1; k < n; k++){
if((lowcost[k] < min) && (!s[k])){
min = lowcost[k];
j = k;
}
}
s[j] = true;//���뵽j ���뵽 s ������4
//sum += min;
for(int k = 1; k < n; k++){
if(table[j][k] < lowcost[k] && (!s[k])){
lowcost[k] = table[j][k];
}
}
}
for(int i = 0; i < n; i++){
sum += lowcost[i];
}
return sum;
}
/**
* �����ǰ���м���Ԫ�ز�Ϊa
* @param next
* @return
*/
private static int getDisc(String str1,String str2) {
int num = 0;
for(int i = 0; i < 7; i++){
if(str1.charAt(i) != str2.charAt(i)){
num++;
}
}
return num;
}
}

```
This entry was posted in poj. Bookmark the permalink.