trang chủ / đề bài / icpc21_reg_a

Bài toán cây khung tuyệt vời

Đề bài

Mô tả

Cho một đồ thị vô hướng liên thông có trọng số gồm N đỉnh và M cạnh. Đồ thị không có khuyên, và giữa hai đỉnh bất kỳ có không quá một cạnh.

Một cạnh được gọi là tuyệt vời nếu có ít nhất một cây khung nhỏ nhất chứa cạnh đó.

Có Q truy vấn. Mỗi truy vấn thêm một cạnh mới vào đồ thị, sau đó bạn cần đếm số cạnh tuyệt vời của đồ thị mới. Lưu ý rằng một cạnh đã được thêm thì ở lại trong đồ thị mãi mãi.

Cây khung nhỏ nhất của một đồ thị vô hướng liên thông có trọng số là một tập con các cạnh nối tất cả các đỉnh với nhau, không tạo chu trình và có tổng trọng số nhỏ nhất có thể.

Ví dụ, xét đồ thị 7 đỉnh với các cạnh (2,7,1), (5,6,3), (4,5,4), (6,7,5), (3,4,5), (1,7,6), (1,2,9), (1,3,9), (1,4,9), (1,5,9), (1,6,9), (2,3,2) (mỗi bộ (u,v,w) là một cạnh nối u và v với trọng số w). Đồ thị này có 2 cây khung nhỏ nhất: cả hai đều chứa các cạnh (2,7), (2,3), (7,1), (6,5), (4,5), và cây thứ nhất chứa thêm (7,6), cây thứ hai chứa thêm (3,4). Đồ thị có 7 cạnh tuyệt vời: (2,7), (2,3), (7,1), (7,6), (3,4), (6,5) và (4,5).

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên N và M, số đỉnh và số cạnh của đồ thị.
  • M dòng tiếp theo, dòng thứ i chứa ba số nguyên ui, vi, wi: có một cạnh nối hai đỉnh ui và vi với trọng số wi trong đồ thị ban đầu.
  • Dòng tiếp theo chứa số nguyên Q, số truy vấn.
  • Q dòng tiếp theo, mỗi dòng chứa ba số nguyên x, y, z mô tả một truy vấn thêm cạnh nối hai đỉnh x và y với trọng số z.

Dữ liệu đảm bảo rằng lúc đầu và sau mỗi truy vấn, đồ thị luôn liên thông và không có hai đỉnh nào được nối bởi nhiều hơn một cạnh.

Dữ liệu ra

Với mỗi truy vấn, in ra một dòng chứa số cạnh tuyệt vời của đồ thị sau truy vấn đó.

Ràng buộc

  • 1≤N,M≤105.
  • 1≤ui,vi≤N, ui≠vi, 0≤wi≤109.
  • 1≤Q≤105.
  • 1≤x,y≤N, x≠y, 0≤z≤109.

Ví dụ

Input Output Giải thích
7 10
2 7 1
5 6 3
4 5 4
6 7 5
3 4 5
1 7 6
1 2 9
1 3 9
1 4 9
1 5 9
2
1 6 9
2 3 2
6
7
Sau truy vấn thứ nhất, các cạnh tuyệt vời là (2,7), (5,6), (4,5), (6,7), (3,4), (1,7). Sau truy vấn thứ hai, đồ thị chính là đồ thị trong phần mô tả.
3 2
1 2 5
2 3 5
1
1 3 5
3 Ví dụ bổ sung (không có trong đề gốc). Ba cạnh cùng trọng số tạo thành một chu trình, mỗi cạnh đều nằm trong một cây khung nhỏ nhất nào đó.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0