POJ2485 (árbol de span mínimo)

Carreteras

Descripción

La nación insular de Flatopia es perfectamente plana. Desafortunadamente, Flatopia no tiene carreteras públicas. Así que el tráfico es difícil en Flatopia. El gobierno flatopiano es consciente de este problema. Están planeando construir algunas carreteras para que sea posible conducir entre cualquier par de ciudades sin salir del sistema de carreteras.

Las ciudades flatopianas están numeradas del 1 al N. Cada autopista conecta exactamente dos ciudades. Todas las carreteras siguen líneas rectas. Todas las carreteras se pueden utilizar en ambas direcciones. Las autopistas pueden cruzarse libremente entre sí, pero un conductor sólo puede cambiar entre carreteras en una ciudad que se encuentra al final de ambas autopistas.

El gobierno flatopiano quiere minimizar la longitud de la carretera más larga que se construirá. Sin embargo, quieren garantizar que cada ciudad es accesible desde cualquier otra ciudad.

Entrada

La primera línea de entrada es una T entera, que indica cuántos casos de prueba siguieron.
La primera línea de cada caso es un entero N (3 <= N <= 500), que es el número de aldeas. A continuación, vienen las líneas N, la i-th de la cual contiene enteros N, y la j-th de estos enteros N es la distancia (la distancia debe ser un entero dentro de [1, 65536]) entre el pueblo i y el pueblo j. Hay una línea vacía después de cada caso de prueba.

Salida

Para cada caso de prueba, debe generar una línea que contenga un entero, que es la longitud de la carretera más larga que se va a construir de modo que todas las aldeas estén conectadas y este valor sea mínimo.

Patrón de diseño-patrón singleton

Entrada de muestra

Salida de muestra

Significado

El número de ciudades del 1 al N. Cada autopista está conectando dos ciudades. Todos los caminos son rectos. Todos los caminos pueden ser bidireccionales. La autopista puede ser de cruce libre, pero el conductor puede cambiar entre las autopistas situadas al final de las dos autopistas. El Gobierno de Flatobang espera acortar la longitud de la construcción de la carretera más larga. Sin embargo, quieren asegurarse de que cada ciudad pueda llegar de otras ciudades.

Pensar

Introduzca una imagen de una matriz de adyacencia, que es la longitud del máximo de la generación máxima del diagrama de generación mínima (N-1).

Código

import java.util.Scanner;
public class Highways {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int m = sc.nextInt();
    for (int i = 0; i < m; i++) {
      int n = sc.nextInt();
      int[][] graph = new int[n][n];
      for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
          graph[j][k] = sc.nextInt();
        }
      }
      int result = prim(graph, 0);
      System.out.println(result);
    }
  }

  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;
        }
      }
      if (result < minDis) {
        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;
  }
}