VM 15 Bài 03 - Cắt đồ thị

View as PDF

Submit solution

Points: 2.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
VM15 - Nguyễn Vương Linh
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho một đơn đồ thị vô hướng ~G~ = ~(V~, ~E)~ có ~N~ đỉnh và ~M~ cạnh. Với mỗi tập con ~H~ của ~V~, gọi ~G~ ~(H)~ là đồ thị thu được từ việc xoá tất cả các đỉnh và các cạnh có ít nhất ~1~ đầu mút không thuộc ~H~. Tập ~H~ được gọi là liên thông, nếu như ~G~ ~(H)~ liên thông. Gọi ~D~ ~(H)~ là giá trị lát cắt ứng với ~H~: số lượng cạnh ~(u~, ~v)~ thoả mãn ~1~ trong ~2~ đỉnh thuộc tập ~H~, và đỉnh còn lại không thuộc tập ~H~ ~(u~ thuộc ~H~ và ~v~ không thuộc ~H~, hoặc ~v~ thuộc ~H~ và ~u~ không thuộc ~H)~. Nói cách khác, ~D~ ~(H)~ là số cạnh tối thiểu cần xoá sao cho ~H~ và ~(G~ - ~H)~ không còn liên thông với nhau ~(G~ - ~H)~ là đồ thị nhận được khi xóa các đỉnh của ~H~ và các cạnh tương ứng ra khỏi ~G)~.

Xác định tập ~H~ liên thông sao cho ~D(H)~ lớn nhất có thể.

Input

  • Dòng ~1~: chứa ~2~ số nguyên dương ~N~ và ~M~ ~\left(1 \leq N \leq 200, 0 \leq M \leq \frac{N \times (N - 1)}{2}\right)~.
  • ~M~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên ~u~ và ~v~ thể hiện đồ thị có cạnh nối trực tiếp giữa ~u~ và ~v~.
  • Dữ liệu đảm bảo không có cạnh nào xuất hiện ~2~ lần trong input

Output

  • Dòng ~1~: Giá trị của ~D(H)~.
  • Dòng ~2~: Kích thước tập ~H~.
  • Dòng ~3~: Những đỉnh thuộc tập ~H~, mỗi số cách nhau bởi một khoảng trắng.

Cách tính điểm

Với mỗi test:

  • Gọi ~D1(H)~ là giá trị ~D(H)~ của bạn, ~D2(H)~ là giá trị ~D(H)~ của BTC, ~P~ là điểm của test.
  • Nếu giá trị ~D(H)~ và tập ~H~ của bạn hợp lệ. Điểm của bạn sẽ là: ~\min \left(\frac{D1(H)}{D2(H)} \times P \times 95\%, P \right)~.
  • Nếu tập ~H~ của bạn không hợp lệ, bạn đuợc 0 điểm.

Sample Input

5 6
1 2
2 3
3 1
2 4
3 5
4 5

Sample Output

4
2
2 3

Comments

Please read the guidelines before commenting.


There are no comments at the moment.