Không hỗ trợ Mobile

Chế độ luyện tập yêu cầu môi trường màn hình lớn để làm bài và chống gian lận hiệu quả. Vui lòng truy cập bằng máy tính (Desktop/Laptop) để tiếp tục thao tác.

Quay lại trang chủ

#2022 · Mạng lưới khoảng cách bí ẩn

Trong một hệ thống mạng thông minh của tương lai, các trạm được kết nối với nhau bằng các tuyến đường đặc biệt tạo thành một cấu trúc cây.

Mỗi tuyến đường có một độ dài (trọng số), và dữ liệu hệ thống chỉ lưu lại khoảng cách giữa các cặp trạm, thay vì cấu trúc kết nối ban đầu.

Do một sự cố, toàn bộ sơ đồ mạng đã bị mất, chỉ còn lại bảng khoảng cách giữa các trạm.

Bạn được cung cấp một số nguyên N - số lượng trạm.

Với mỗi cặp (i, j) $(1 \le i < j \le N)$, bạn biết: $A_{i,j}$ là khoảng cách giữa trạm $i$ và trạm $j$.

Khoảng cách này được định nghĩa là:

\text{dist}(i,j) = \sum \text{trọng số các cạnh trên đường đi duy nhất giữa } i \text{ và } j

Hãy xác định xem: Có tồn tại một cây vô hướng có trọng số dương gồm N đỉnh sao cho mọi khoảng cách thực tế đều đúng bằng A_{i,j} hay không?

Dữ liệu vào

  • Dòng 1: số nguyên N
  • Các dòng tiếp theo:

A_{1,2}, A_{1,3}, \dots, A_{1,N}

A_{2,3}, \dots, A_{2,N}

\dots

A_{N-1,N}

Dữ liệu ra

  • In Yes nếu tồn tại cây phù hợp\
  • Ngược lại in No

Ràng buộc

  • 2 \le N \le 3000
  • 1 \le A_{i,j} \le 9999

BẢNG TỔNG QUAN KẾT QUẢ

# Tài khoản Kết suất Lúc nộp
1
Lê Văn Nguyên @35261020087
1 ms 264 KB
1530 Bytes
05/05/2026
20:09
2
1 ms 284 KB
1842 Bytes
22/04/2026
14:37
3
1 ms 284 KB
2544 Bytes
21/04/2026
23:53
4
1 ms 300 KB
1601 Bytes
23/04/2026
08:57
5
1 ms 300 KB
2274 Bytes
27/05/2026
10:07
6
Lê Duy Hải @2280600799
1 ms 300 KB
2332 Bytes
23/04/2026
03:27
7
Lê Duy Hải @2280600799
1 ms 300 KB
2332 Bytes
24/04/2026
17:36
8
Lê Duy Hải @2280600799
1 ms 300 KB
2332 Bytes
25/04/2026
22:28
9
1 ms 304 KB
2274 Bytes
25/05/2026
09:23
10
1 ms 304 KB
2274 Bytes
29/05/2026
13:20
11
1 ms 304 KB
2316 Bytes
28/05/2026
14:11
12
1 ms 396 KB
1779 Bytes
22/04/2026
00:09
13
1 ms 400 KB
1779 Bytes
21/04/2026
23:58
14
1 ms 408 KB
1779 Bytes
24/04/2026
09:28
15
Đỗ Chí Thành @24800600886
1 ms 412 KB
1922 Bytes
22/04/2026
17:38
16
2 ms 300 KB
2274 Bytes
29/05/2026
13:20
17
39 ms 3448 KB
1379 Bytes
27/04/2026
09:20
18
42 ms 3440 KB
1473 Bytes
22/04/2026
16:12
19
179 ms 13940 KB
2746 Bytes
24/04/2026
14:51

LỊCH SỬ CÁ NHÂN

Vui lòng đăng nhập để xem lịch sử làm bài của bạn.

THẢO LUẬN BÀI TOÁN

4 ngày trước

Tham khảo code Python

import sys

def bai2022():

dulieu = sys.stdin.read().split()
if not dulieu:
    return

n = int(dulieu[0])
if n == 1:
    print("Yes")
    return

dist = [[0] * (n + 1) for _ in range(n + 1)]
bien = 1
for i in range(1, n):
    for j in range(i + 1, n + 1):
        giatri = int(dulieu[bien])
        dist[i][j] = dist[j][i] = giatri
        bien += 1
        if giatri <= 0:
            print("No")
            return

for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        for k in range(j + 1, n + 1):
            s1 = dist[i][j] + dist[k][1] if k != 1 and i != 1 and j != 1 else -1
            val = dist[1][i] + dist[1][j] - dist[i][j]
            if val < 0 or val % 2 != 0:
                print("No")
                return
            
for i in range(2, n + 1):
    for j in range(i + 1, n + 1):
        for k in range(j + 1, n + 1):
            s1 = dist[i][j] + dist[1][k]
            s2 = dist[i][k] + dist[1][j]
            s3 = dist[j][k] + dist[1][i]
            
            sums = sorted([s1, s2, s3])
            if sums[1] != sums[2]:
                print("No")
                return

print("Yes")

if name == "main":

bai2022()
Vào thảo luận 1 Phản hồi
8 ngày trước

Tham khảo code C

include <stdio.h>

int mt[3000][3000]; int kc[3000]; int dd[3000]; int tr[3000];

int dc[3000]; int nc[6005]; int tc[6005]; int ts[6005]; int sm = 0;

static inline void tmc(int u, int v, int w) {

++sm;
tc[sm] = v;
ts[sm] = w;
nc[sm] = dc[u];
dc[u] = sm;

}

static inline int ds() {

int k = 0, c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') {
    k = k * 10 + c - '0';
    c = getchar();
}
return k;

}

int hd[3000]; int kct[3000];

int main() {

int sn = ds();
for (int i = 0; i < sn - 1; ++i) {
    for (int j = i + 1; j < sn; ++j) {
        mt[i][j] = ds();
        mt[j][i] = mt[i][j];
    }
}

for (int i = 0; i < sn; ++i) {
    kc[i] = 1000000000;
    dd[i] = 0;
    tr[i] = -1;
}

kc[0] = 0;

for (int i = 0; i < sn; ++i) {
    int u = -1;
    for (int j = 0; j < sn; ++j) {
        if (!dd[j] && (u == -1 || kc[j] < kc[u])) {
            u = j;
        }
    }

    if (kc[u] == 1000000000) {
        puts("No");
        return 0;
    }

    dd[u] = 1;
    if (tr[u] != -1) {
        if (kc[u] <= 0) {
            puts("No");
            return 0;
        }
        tmc(tr[u], u, kc[u]);
        tmc(u, tr[u], kc[u]);
    }

    for (int v = 0; v < sn; ++v) {
        if (!dd[v] && mt[u][v] < kc[v]) {
            kc[v] = mt[u][v];
            tr[v] = u;
        }
    }
}

for (int i = 0; i < sn; ++i) {
    for (int j = 0; j < sn; ++j) kct[j] = -1;
    int d = 0, c = 0;
    hd[c++] = i;
    kct[i] = 0;

    while (d < c) {
        int u = hd[d++];
        for (int e = dc[u]; e; e = nc[e]) {
            int v = tc[e];
            if (kct[v] == -1) {
                kct[v] = kct[u] + ts[e];
                hd[c++] = v;
            }
        }
    }

    for (int j = 0; j < sn; ++j) {
        if (kct[j] != mt[i][j]) {
            puts("No");
            return 0;
        }
    }
}

puts("Yes");
return 0;

}

Vào thảo luận 0 Phản hồi

GỢI Ý & HƯỚNG DẪN

Giải thích ví dụ 1:

  • Kết nối trạm 1 với trạm 2 bằng một cạnh có độ dài 2
  • Kết nối trạm 2 với trạm 3 bằng một cạnh có độ dài 3
  • Kết nối trạm 2 với trạm 4 bằng một cạnh có độ dài 2

Khi đó, ta kiểm tra lại khoảng cách giữa các cặp trạm:

  • Khoảng cách giữa 1 và 2 là 2
  • Khoảng cách giữa 1 và 3 là 2+3=5
  • Khoảng cách giữa 1 và 4 là 2+2=4
  • Khoảng cách giữa 2 và 3 là 3
  • Khoảng cách giữa 2 và 4 là 2
  • Khoảng cách giữa 3 và 4 là 3+2=5
Viết code