VMCUT - Cắt đồ thị
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274709/problem/L
https://codeforces.com/group/FLVn1Sc504/contest/272945/problem/C
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ể.
Cách tính điểm:
- Với mỗi 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à D(H) bạn / D(H) ban tổ chức . Ngược lại, bạn đuợc 0 điểm.
Input
- Dòng 1: chứa 2 số nguyên dương N và M (1 ≤ N ≤ 200, 0 ≤ M ≤ N * ( N - 1) / 2).
- 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.
Chấm điểm
- Trong quá trình thi, bài của bạn được chấm với 20% test. Sau khi kỳ thi kết thúc, bài của bạn sẽ được chấm lại với toàn bộ 100% test.
- Chú ý, test ví dụ phía dưới không nằm trong 20% test.
Ví dụ
Input
5 6 1 2 2 3 3 1 2 4 3 5 4 5
Output 1
4 2 2 3
Output 2
2 3 1 2 3
- Người up: voj
- Nguồn bài: VM15 - Nguyễn Vương Linh