noj 布线问题

本文主要是介绍noj 布线问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最小生成树。

import java.util.Arrays;
import java.util.Scanner;
public class Main 
{
static int prim(int n,int [][]adj)
{
int sum=0;
int lowcost[]=new int[n+1];
boolean s[]=new boolean[n+1];
s[1]=true;
for(int i=2;i<=n;i++)lowcost[i]=adj[1][i];
for(int i=1;i<n;i++)
{
int min=Integer.MAX_VALUE;
int low=1;
for(int k=2;k<=n;k++) 
{
if(!s[k] &&lowcost[k]<min)
{
min=lowcost[k];
low=k;
}
}
s[low]=true;
sum+=min;
for(int k=2;k<=n;k++)
{
if(!s[k]&&adj[low][k]<lowcost[k])
{
lowcost[k]=adj[low][k];
}
}
}
return sum;
}
public static void main(String[] args)
{
Scanner cin=new Scanner(System.in);
int a[]=new int[3];
int n=cin.nextInt();
while(n--!=0)
{
int p=cin.nextInt();
int r=cin.nextInt();
int sum=Integer.MAX_VALUE;
int adj[][]=new int[p+1][p+1];
for(int i=0;i<=p;i++) Arrays.fill(adj[i], Integer.MAX_VALUE);
for(int i=0;i<r;i++)
{
for(int j=0;j<3;j++) a[j]=cin.nextInt();
if(adj[a[0]][a[1]]>a[2])adj[a[0]][a[1]]=adj[a[1]][a[0]]=a[2];
}
for(int i=0;i<p;i++)
{
int dis=cin.nextInt();
sum=Math.min(sum, dis);
}
if(sum==Integer.MAX_VALUE) sum=0;
if(r==0) {System.out.println(sum);continue;}
System.out.println(sum+prim(p,adj));
}
}
}

 

这篇关于noj 布线问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---