Vùng có tổng chi phí nhỏ hơn hoặc bằng S

View as PDF

Submit solution

Points: 100.00 (partial)
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Vùng liên thông trong đồ thị là tập hợp các đỉnh mà từ một đỉnh bất kỳ có đường đi trực tiếp hoặc gián tiếp đến các đỉnh khác trong tập hợp đó. Cho đồ thị vô hướng có N đỉnh, M cạnh. Các đỉnh được đánh số từ 1 tới N. Chi phí thăm đỉnh thứ iti. Hãy tìm các vùng liên thông có tổng chi phí nhỏ hơn hoặc bằng S.

Dữ liệu vào gồm:

  • Dòng 1: Ghi số nguyên dương N,MS (M,N3000,S109).
  • Dòng 2: Ghi N số nguyên dương ti là chi phí thăm đỉnh i (ti109).
  • M dòng tiếp theo, mỗi dòng ghi số nguyên dương uv thể hiện có đường đi giữa hai đỉnh uv (u,vN).

Kết quả: Ghi ra các vùng liên thông tìm được. Mỗi vùng liên thông ghi trên một hàng. Mỗi số cách nhau một dấu cách. Nếu không có ghi ra 1.

Ví dụ:
INPUT
Copy
12 7 5
1 2 3 1 2 4 4 4 3 3 2 1
1 2
2 5
2 6
6 10
3 4
9 11
9 12
OUTPUT
Copy
3 4
7
8

Comments

Please read the guidelines before commenting.