|
|
#include <algorithm>
#include <iostream>
using namespace std;
int fa[1010]; // 定义父亲
int n, m, k;
struct edge {
int u, v, w;
int l;
edge g[10010];
void add(int u, int v, int w) {
l++;
g[l].u = u;
g[l].v = v;
g[l].w = w;
// 标准并查集
int findroot(int x) { return fa[x] == x ? x : fa[x] = findroot(fa[x]); }
void Merge(int x, int y) {
x = findroot(x);
y = findroot(y);
fa[x] = y;
bool cmp(edge A, edge B) { return A.w < B.w; }
// Kruskal 算法
void kruskal() {
int tot = 0; // 存已选了的边数
int ans = 0; // 存总的代价
for (int i = 1; i <= m; i++) {
int xr = findroot(g[i].u), yr = findroot(g[i].v);
if (xr != yr) { // 如果父亲不一样
Merge(xr, yr); // 合并
tot++; // 边数增加
ans += g[i].w; // 代价增加
if (tot >= (n - k)) { // 检查选的边数是否满足 k 个棉花糖
cout << ans << '\n';
return;
cout << "No Answer\n"; // 无法连成
int main() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) { // 初始化
fa[i] = i;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
add(u, v, w); // 添加边
sort(g + 1, g + m + 1, cmp); // 先按边权排序
kruskal();
return 0;
55
|
class Edge:
def __init__(self, u, v, w):
self.u = u
self.v = v
self.w = w
fa = [0] * 1010 # 定义父亲
g = []
def add(u, v, w):
g.append(Edge(u, v, w))
# 标准并查集
def findroot(x):
if fa[x] == x:
return x
fa[x] = findroot(fa[x])
return fa[x]
def Merge(x, y):
x = findroot(x)
y = findroot(y)
fa[x] = y
# Kruskal 算法
def kruskal():
tot = 0 # 存已选了的边数
ans = 0 # 存总的代价
for e in g:
x = findroot(e.u)
y = findroot(e.v)
if x != y: # 如果父亲不一样
fa[x] = y # 合并
tot += 1 # 边数增加
ans += e.w # 代价增加
if tot >= (n - k): # 检查选的边数是否满足 k 个棉花糖
print(ans)
return
print("No Answer") # 无法连成
if __name__ == "__main__":
n, m, k = map(int, input().split())
for i in range(1, n + 1): # 初始化
fa[i] = i
for i in range(1, m + 1):
u, v, w = map(int, input().split())
add(u, v, w) # 添加边
g.sort(key=lambda edge: edge.w) # 先按边权排序
kruskal()
86
|
import java.util.Arrays;
import java.util.Scanner;
class Edge {
int u;
int v;
int w;
Edge(int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
public class Main {
static int[] parent = new int[1010]; // 定义父亲
static int m, n, k; // n 表示点的数量， m 表示边的数量，k 表示需要的棉花糖个数
static Edge[] edges = new Edge[10010];
static int l;
static void addEdge(int u, int v, int w) {
edges[++l] = new Edge(u, v, w);
// 标准并查集
static int findroot(int x) {
if (parent[x] != x) {
parent[x] = findroot(parent[x]);
return parent[x];
static void Merge(int x, int y) {
x = findroot(x);
y = findroot(y);
parent[x] = y;
static boolean cmp(Edge A, Edge B) {
return A.w < B.w;
// Kruskal 算法
static void kruskal() {
int tot = 0; // 存已选了的边数
int ans = 0; // 存总的代价
for (int i = 1; i <= m; i++) {
int xr = findroot(edges[i].u);
int yr = findroot(edges[i].v);
if (xr != yr) { // 如果父亲不一样
Merge(xr, yr); // 合并
tot++; // 边数增加
ans += edges[i].w; // 代价增加
if (tot >= (n - k)) { // 检查选的边数是否满足 k 个棉花糖
System.out.println(ans);
return;
System.out.println("No Answer"); // 无法连成
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
k = scanner.nextInt();
// 初始化
for (int i = 1; i <= n; i++) {
parent[i] = i;
for (int i = 1; i <= m; i++) {
int u = scanner.nextInt();
int v = scanner.nextInt();
int w = scanner.nextInt();
addEdge(u, v, w); // 添加边
Arrays.sort(edges, 1, m + 1, (a, b) -> Integer.compare(a.w, b.w)); // 先按边权排序
kruskal();
scanner.close();
|
