最小生成树———灌溉

雨点打透心脏的1/2处 2022-06-07 12:17 143阅读 0赞

到了旱季农业生产的灌溉就成了一个大问题。为了保证灌溉的顺利，某县政府决定投资为各个村之间建立灌溉管道。

输入第1行包括一个整数N，表示某县的村庄的数量。（3≤N≤100），第2行-结尾为一个N×N的矩阵,表示每个村庄之间的距离。虽然在理论上，他们是N行，每行由N个用空格分隔的数组成，实际上，他们限制在80个字符，因此，某些行会紧接着另一些行。当然，对角线将会是0，因为不会有线路从第i个村到它本身（任何两个村之间的距离都不大于100000）。

输出只有一个，为修建灌溉管道将所有村庄相连在一个灌溉系统里所需的最小管道长度。

#### 样例输入 ####

4
    0 4 9 21
    4 0 8 17
    9 8 0 16
    21 17 16 0

#### 样例输出 ####

import java.util.Scanner;

public class Main \{  
   
 public static int PRIM(int \[\]\[\] graph,int n)\{  
  int\[\] dis=new int\[110\];  
  int\[\] vis=new int\[110\];  
  for(int i=1;i<=n;i++) \{  
   dis\[i\]=graph\[1\]\[i\];  
   vis\[i\]=0;  
  \}  
  dis\[1\]=0;  
  vis\[1\]=1;  
  int sum=0,index=0;  
  for(int i=1;i<n;i++)\{  
   int minW=Integer.MAX\_VALUE;  
   for(int j=1;j<=n;j++)\{  
      
       if(vis\[j\]==0 && minW>dis\[j\])\{  
     minW=dis\[j\];  
     index=j;  
    \}  
   \}  
   vis\[index\]=1;  
   //System.out.println(minW);  
   sum+=minW;  
   for(int j=1;j<=n;j++)\{//更新mins数  
     if( vis\[j\]==0 && graph\[index\]\[j\]<dis\[j\])\{  
      dis\[j\]=graph\[index\]\[j\];  
     \}  
   \}  
  \}  
  return sum;  
 \}  
 public static void main(String \[\] args)\{  
  Scanner sc=new Scanner(System.in);  
  int n,s;  
  int \[\]\[\] tree=new int\[110\]\[110\];  
  n=sc.nextInt();  
  //System.out.println(n);  
  for(int i=1;i<=n;i++) \{  
   for(int j=1;j<=n;j++) \{  
    tree\[i\]\[j\]=sc.nextInt();  
   \}  
  \}  
  s=Main.PRIM(tree, n);  
  System.out.println(s);  
 \}  
\}