AcWing 858. Prim算法求最小生成树java
原题链接
简单
作者:
huaqingren
,
2021-02-09 20:13:30
,
所有人可见
,
阅读 227
import java.util.Scanner;
public class Main
{
private static int N=510;
private static int n,m;
private static int[][] g=new int[N][N];
private static boolean[] st=new boolean[N];
private static int[] dist=new int[N];
private static int max=100000000;
public static void main(String[] args)
{
Scanner scan=new Scanner(System.in);
n=scan.nextInt();
m=scan.nextInt();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i==j)
g[i][j]=0;
else
g[i][j]=max;
}
//初始化每个点到已选择点的集合的距离
for(int i=1;i<=n;i++)
dist[i]=max;
for(int i=0;i<m;i++)
{
int a=scan.nextInt();
int b=scan.nextInt();
int c=scan.nextInt();
g[a][b]=g[b][a]=Math.min(g[a][b], c);
}
int t=prim();
if(t==max)
System.out.println("impossible");
else
System.out.println(t);
scan.close();
}
private static int prim()
{
int res=0;
for(int i=0;i<n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
{
if(!st[j]&&(t==-1||dist[t]>dist[j]))
t=j;
}
if(i!=0&&dist[t]==max) return max;
if(i!=0)
res+=dist[t];
for(int j=1;j<=n;j++)
dist[j]=Math.min(dist[j], g[t][j]);
st[t]=true;
}
return res;
}
}