1 liên kết câu hỏi gốc

Đường Rừng - POJ 1251 - Thẩm phán ảo

https://vjudge.net/problem/POJ-1251

2. Đầu vào và đầu ra

1 đầu vào

Dữ liệu đầu vào bao gồm các tập dữ liệu từ 1 đến 100, với hàng cuối cùng chỉ chứa 0. Hàng đầu tiên của mỗi tập dữ liệu là một số n, cho biết số làng và các làng được đánh dấu bằng n chữ cái viết hoa đầu tiên của bảng chữ cái. Mỗi tập dữ liệu được mô tả bằng n-1 hàng được sắp xếp theo thứ tự bảng chữ cái theo nhãn làng. Ngôi làng cuối cùng không có đường. Mỗi con đường trong làng bắt đầu bằng một nhãn làng, theo sau là con đường số k từ làng này đến làng sau. Nếu k>0 thì theo sau hàng đó là k con đường từ làng này đến làng sau. Nếu k>0 thì hàng chứa k dữ liệu đường. Dữ liệu cho mỗi con đường là nhãn ở đầu bên kia của con đường, sau đó là chi phí bảo trì đường hàng tháng.

2 đầu ra

Đối với mỗi tập dữ liệu, xuất ra một hàng duy nhất để biết chi phí duy trì hàng tháng tối thiểu cho một con đường nối tất cả các làng.

Ba ví dụ đầu vào và đầu ra

1 mẫu đầu vào

9

A 2 B 12 Tôi 25

B 3 C 10 H 40 I 8

C 2 D 18 G 55

D 1 E 44

E 2 F 60 G 38

F 0

G 1 H 35

H 1 tôi 35

3

A 2 B 10 C 40

B 1 C 20

0

2 Mẫu đầu ra

216

30

Bốn phân tích

Đây là bài toán cây khung nhỏ nhất rất đơn giản, chỉ cần tính tổng các cây khung nhỏ nhất. Nó có thể được giải bằng thuật toán Prim hoặc Kruskal.

Năm mã

gói graph.poj1251; nhập java.util.Scanner; lớp công khai Poj1251 { static int[] m[] = new int[30][30]; static int dis[] = new int boolean vis[] ; int tĩnh n; tĩnh int prim(int s) { for (int i = 0; i < n; i++) dis[i] = m[s][i]; vis = new boolean[30]; vis[s] = true; int sum = 0; for (int i = 1; i < n; i++) { int min = 0x3f3f3f3f; for (int j = 0; j < n; j++) { // Tìm giá trị nhỏ nhất if (!vis[j] && dis[j] < min) { min = dis[j]; t = j; } } sum += min; vis[t] = true; for (int j = 0; j < n; j++) { // cập nhật if (!vis[j] && dis[ j] > m[t][j]) dis[j] = m[t][j]; } } return sum; } public static void main(String[] args) { Máy quét quét = Máy quét mới(System.in ); trong khi (true) { n = scanner.nextInt(); if (n == 0) { return; } int num, w; for (int i = 0; i < m.length; i++) { for (int j = 0; j < m[0].length; j++) { m[i][j] = 0x3f3f3f3f; // Gán các giá trị riêng biệt} } cho (int i = 1; i < n; i++) { c = scanner.next().charAt(0); num = scanner.nextInt(); int u = c - 'A'; while (num-- > 0) { c = scanner.next(). charAt(0); w = scanner.nextInt(); int v = c - 'A'; w; } } System.out.println(prim(0)); } } }

Sáu bài kiểm tra

Màu xanh lá cây là đầu ra, màu trắng là đầu ra