AcWing 1141. 局域网
原题链接
简单
作者:
Adam_
,
2022-02-23 21:41:26
,
所有人可见
,
阅读 150
菜鸡写一个Kruskal题,数据结构的模板都封装好了
打完美赛,满血复活!
//其实就是一个Kruskal的板子题
import java.util.*;
class Main {
public static void main(String[] args) {
//处理读入
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
Edge[] edges = new Edge[k];
int sum = 0;
for(int i = 0; i < k; ++i) {
int u = in.nextInt();
int v = in.nextInt();
int w = in.nextInt();
edges[i] = new Edge(u, v, w);
sum += w;
}
//并查集初始化
Arrays.sort(edges);
UF uf = new UF(n);
int ll = 1, idx = 0, f = 0;
while(idx < k && ll < n) {
int u = edges[idx].u;
int v = edges[idx].v;
int w = edges[idx].w;
// System.out.println(w);
if(!uf.connected(u, v)) {
uf.unite(u, v);
f += w;
ll++;
}
idx++;
}
System.out.println(sum - f);
}
}
class Edge implements Comparable{
int u, v, w;
public Edge(int u, int v, int w) {
this.u = u;this.v = v;this.w = w;
}
@Override
public int compareTo(Object o) {
Edge e = (Edge)o;
return w - e.w;
}
}
//并查集模板
class UF {
int[] parent;
int[] size;
int setCount;
public UF (int n) {
parent = new int[n + 1];
size = new int[n + 1];
Arrays.fill(size, 1);
for(int i = 1; i <= n; ++i)
parent[i] = i;
setCount = n;
}
public int findSet(int x) {
return x == parent[x] ? x : (parent[x] = findSet(parent[x]));
}
public boolean unite(int x, int y) {
x = findSet(x);
y = findSet(y);
if(x == y)
return false;
//让x最牛逼
if(size[x] < size[y]) {
x = x ^ y;
y = x ^ y;
x = x ^ y;
}
parent[y] = x;
size[x] += size[y];
--setCount;
return true;
}
public boolean connected(int x, int y) {
return findSet(x) == findSet(y);
}
}