Chiến tranh
Đề bài
Mô tả
Bách thách đố Dương và Thanh chơi một trò chơi. Có một đất nước gồm thành phố, các thành phố được đánh số từ đến . Các thành phố được nối với nhau bằng con đường chiều. Những con đường này sẽ nối giữa thành phố khác nhau và giữa thành phố có thể có nhiều con đường khác nhau.
Hiện tại đất nước đang diễn ra cuộc chiến giữa đội quân và đội quân . Mỗi đội quân có thể di chuyển dọc theo các con đường để đi từ thành phố này sang thành phố khác. Đất nước muốn ngăn chặn chiến tranh diễn ra bằng cách phá hủy một vài con đường sao cho hai đội quân này không thể gặp được nhau và người chơi muốn giảm thiểu tối đa kinh phí để làm việc đó. Hai đội quân có thể gặp nhau khi tồn tại một đường đi gồm các con đường chưa bị phá hủy giữa thành phố mà đội quân này đang chiếm đóng (các con đường trên đường đi có thể qua những thành phố khác).
Người chơi sẽ phải chọn thành phố khác nhau cho đội quân này chiếm đóng và số điểm của người chơi là kinh phí ít nhất để đất nước ngăn chặn chiến tranh. Cả bạn đều muốn số điểm của mình càng thấp càng tốt. Dương là một con người rất thông minh nên cậu dễ dàng tìm được cách chọn thành phố tối ưu nhất. Tuy nhiên Thanh không hiểu về game nên đã chọn ngẫu nhiên thành phố bất kì trong thành phố để làm đáp án: thành phố của đội và thành phố của đội là một cặp có thứ tự gồm hai thành phố khác nhau, mỗi cặp trong cặp được chọn với xác suất như nhau.
Sau cùng, Bách muốn biết số điểm của Dương và trung bình số điểm của Thanh sẽ là bao nhiêu?
Dữ liệu vào
- Dòng đầu tiên ghi số .
- Mỗi dòng trong dòng tiếp theo ghi số chỉ một con đường nối thành phố và và cần đồng tiền để phá hủy con đường đó.
Dữ liệu ra
- Nếu in ra số điểm của Dương.
- Nếu in ra số điểm trung bình của Thanh nhân với . Đảm bảo đáp án cần in ra luôn là số nguyên.
Ràng buộc
- , , .
- , , .
- Nếu thì và .
Subtasks
- Subtask 1 ( số điểm): , .
- Subtask 2 ( số điểm): , .
- Subtask 3 ( số điểm): , , .
- Subtask 4 ( số điểm): , , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 6 9 0 1 1 0 2 7 1 2 1 1 3 3 1 4 2 2 4 4 3 4 1 3 5 6 4 5 2 |
6 | Kinh phí ít nhất để tách từng cặp thành phố với : , , , , , , , , , , , , , , . Chẳng hạn cặp không có con đường nối trực tiếp nhưng vẫn cần đồng: phá các con đường , , (tách khỏi phần còn lại). Dương chọn cặp có kinh phí nhỏ nhất là . |
| 2 6 9 0 1 1 0 2 7 1 2 1 1 3 3 1 4 2 2 4 4 3 4 1 3 5 6 4 5 2 |
190 | Cùng đồ thị. Tổng kinh phí cặp ở trên là ; mỗi cặp xuất hiện hai lần trong cặp có thứ tự, nên đáp án là . |
Bình luận