POJ1789 (árbol de span mínimo)

POJ1789 (árbol de span mínimo)

---

Historia de camiones

Descripción

Advanced Cargo Movement, Ltd. utiliza camiones de diferentes tipos. Algunos camiones se utilizan para la entrega de verduras, otros para muebles, o para ladrillos. La compañía tiene su propio código que describe cada tipo de camión. El código es simplemente una cadena de exactamente siete letras minúsculas (cada letra de cada posición tiene un significado muy especial, pero eso no tiene importancia para esta tarea). Al principio de la historia de la empresa, se utilizó un solo tipo de camión, pero más tarde se derivaron de él otros tipos, luego de los nuevos tipos se derivaron otros tipos, y así sucesivamente.

Hoy en día, ACM es lo suficientemente rico como para pagar a los historiadores para estudiar su historia. Una cosa que los historiadores trataron de averiguar es el llamado plan de derivación, es decir, cómo se derivaron los tipos de camiones. Definieron la distancia de los tipos de camiones como el número de posiciones con diferentes letras en códigos de tipo camión. También asumieron que cada tipo de camión se derivaba exactamente de otro tipo de camión (a excepción del primer tipo de camión que no se derivaba de ningún otro tipo). La calidad de un plan de derivación se definió entonces como
1/Σ(to,td)d(to,td)
donde la suma supera todos los pares de tipos en el plan de derivación de tal manera que es el tipo original y td el tipo derivado de él y d(to,td) es la distancia de los tipos.
Desde que los historiadores fracasaron, debe escribir un programa para ayudarlos. Dados los códigos de tipos de camiones, su programa debe encontrar la más alta calidad posible de un plan de derivación.

Entrada

La entrada consta de varios casos de prueba. Cada caso de prueba comienza con una línea que contiene el número de tipos de camiones, N, 2 <= N <= 2 000. Cada una de las siguientes líneas N de entrada contiene un código de tipo de camión (una cadena de siete letras minúsculas). Usted puede asumir que los códigos describen únicamente los camiones, es decir, no hay dos de estas líneas N son los mismos. La entrada se termina con cero en el lugar de número de tipos de camiones.

Salida

Para cada caso de prueba, su programa debe emitir el texto «La más alta calidad posible es 1/Q.», donde 1/Q es la calidad del mejor plan de derivación.

Entrada de muestra

4
aaaaaaa
baaaaaa
abaaaaa
aabaaaa
0

Salida de muestra

The highest possible quality is 1/3.

Significado

Históricamente, se han utilizado 7 letras minúsculas para representar cada modelo TRUCK, y la brecha entre los dos modelos es el número de letras diferentes en las letras. Ahora dale a N diferentes modelos de TRUCK, cómo hacer

** 1 / σ (TO, TD) D (TO, TD) ** se minimiza.

Pensar

Para cada entrada de línea, se ve como un punto. Y diferentes letras de las otras entradas son a otros puntos. Hay un camino entre dos puntos cualquiera, que es una imagen completa.

En la figura completa, el peso es el número de letras diferentes. Buscando árboles de expansión mínimos.

Código

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class TruckHistory {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    while (true) {
      int n = sc.nextInt();
      if (n == 0) {
        break;
      }
      List<String> strs = new ArrayList<String>();
      for (int i = 0; i < n; i++) {
        String str = sc.next();
        strs.add(str);
      }
      int[][] graph = new int[n][n];
      for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
          if (i == j) {
            graph[i][j] = 0;
          } else {
            char[] a = strs.get(i).toCharArray();
            char[] b = strs.get(j).toCharArray();
            int w = 0;
            for (int k = 0; k < a.length; k++) {
              if (a[k] != b[k]) {
                w++;
              }
            }
            graph[i][j] = w;
            graph[j][i] = w;
          }
        }
      }
      int sum = prim(graph, 0);
      System.out.println("The highest possible quality is 1/" + sum + ".");
    }
  }

  public static int prim(int[][] graph, int startPoint) {
    int result = 0;

    int[] lowcost = new int[graph.length];
    int[] closest = new int[graph.length];
    int minDis = Integer.MAX_VALUE;

    for (int i = 0; i < lowcost.length; i++) {// Lowcost and Closest initial value
      lowcost[i] = graph[startPoint][i];
      closest[i] = startPoint;
    }

    for (int i = 0; i < lowcost.length - 1; i++) {/ / In addition to N-1 point outside STARTPOINT
      minDis = Integer.MAX_VALUE;
      int index = startPoint;
      for (int j = 0; j < lowcost.length; j++) {
        if (lowcost[j] != 0 && lowcost[j] < minDis) {
          minDis = lowcost[j];
          index = j;
        }
      }
      result = result + minDis;
      lowcost[index] = 0;
      for (int j = 0; j < lowcost.length; j++) {/ / Update Lowcost and Closest
        if (graph[index][j] != 0 && graph[index][j] < lowcost[j]) {
          lowcost[j] = graph[index][j];
          closest[j] = index;
        }
      }
    }
    return result;
  }
}