AcWing 859. Kruskal算法求最小生成树java
原题链接
简单
作者:
huaqingren
,
2021-02-09 20:37:44
,
所有人可见
,
阅读 443
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main
{
private static int N=100010;
private static int M=200010;
private static int max=1000000000;
private static int[] p=new int[N];
private static int n,m;
static Comparator<node> cmp=new Comparator<node>()
{
//将两边的权值按照从小到大排序
@Override
public int compare(node o1, node o2)
{
return o1.c-o2.c;
}
};
public static void main(String[] args)
{
Scanner scan=new Scanner(System.in);
n=scan.nextInt();
m=scan.nextInt();
node[] edges=new node[m];
for(int i=0;i<m;i++)
{
int a=scan.nextInt();
int b=scan.nextInt();
int c=scan.nextInt();
edges[i]=new node(a,b,c);
}
Arrays.sort(edges, cmp);
for(int i=1;i<=n;i++) p[i]=i; //初始化并查集
int cnt=0,res=0;
for(int i=0;i<m;i++)
{
node t=edges[i];
int a=t.a,b=t.b,c=t.c;
int fa=find(a),fb=find(b);
if(fa!=fb)
{
p[fa]=fb;
cnt++;
res+=c;
}
//需要选中n-1条边构成树
if(cnt==n-1)
break;
}
if(cnt==n-1)
System.out.println(res);
else
System.out.println("impossible");
scan.close();
}
private static int find(int x)
{
while(x!=p[x])
{
p[x]=p[p[x]];
x=p[x];
}
return x;
}
private static class node
{
private int a;
private int b;
private int c;
public node(int a, int b, int c)
{
super();
this.a = a;
this.b = b;
this.c = c;
}
}
}