Nguồn: Đề kiểm tra đội tuyển Tin học
Hòa Bình
Sau khi phá tan lũ quái vật ở vùng biên
giới, nhà vua quyết định mở cuộc tấn công tới tận hang ổ của bọn chúng. Hệ thống
phòng thủ của lũ quái vật rất kiên cố và phức tạp. Bọn chúng xây dựng các lâu
đài, và giữa một số cặp lâu đài, chúng đắp thành lũy liên kết với nhau, để bảo
vệ cho các đội quân nằm bên trong, không có lâu đài nào không có thành lũy liên
kết tới các lâu đài khác. Hang ổ của quân địch cứ tầng tầng lớp lớp.
Nhà vua đã vạch ra kế hoạch như sau:
+ Bước 1: Dùng máy bắn đá phá vỡ một số thành trì liên kết giữa các
lâu đài của bọn chúng, sao cho không có đội quân nào của địch được bảo vệ kín bởi
hệ thống thành trì.
+ Bước 2: Tiến công đánh giáp lá cà với quân địch.
Trong các lâu đài, lũ quái vật chuẩn bị
rất nhiều các máy bắn đá. Để đảm báo phá được một thành lũy, nhà vua yêu cầu cần
sử dụng số máy bắn đá bằng với tổng số máy bắn đá mà hai lâu đài ở 2 đầu thành
lũy của địch. Chẳng hạn nếu lâu đài A có 5 máy bắn đá, lâu đài B có 3 máy bắn
đá, để phá được bức tường thành nối lâu đài A và lâu đài B, đội quân của nhà
vua cần sử dụng ít nhất 5+3 = 8 máy bắn đá.
Hình vẽ minh họa cho một hệ thống lâu
đài + thành lũy của quân địch. Khi phá bức tường thành liên kết giữa 2 cặp lâu
đài có số lượng máy bắn đá là (1,1), sẽ sử dụng số máy bắn đá là ít nhất (4
cái). Khi đó, không còn đội quân nào được bao bọc kín bởi thành lũy nữa, quân đội
của nhà vua sẽ sẵn sàng vào tấn công giáp lá cà.
Các bạn hãy giúp nhà vua tính toán xem,
cần sử dụng ít nhất bao nhiêu máy bắn đá để thực hiện được bước 1 của chiến dịch.
Dữ liệu
vào: Từ tệp văn bản ATTACK.INP
+ Dòng đầu tiên gồm 2 số nguyên N và M
(2 <= N <= 105, 1 <= M <= 105) là số lâu đài
của quân địch và số thành lũy liên kết một số lâu đài.
+ Dòng thứ hai chứa N số nguyên, số thứ
i biểu diễn số lượng máy bắn đá của địch có trong lâu đài thứ i.
+M dòng tiếp theo, mỗi dòng chứa 2 số nguyên
(u,v) biểu diễn một thành lũy liên kết một cặp lâu đài của quân địch.
Dữ liệu
ra: ghi vào tệp văn bản ATTACK.OUT
+ In ra tổng số số máy bắn đá ít nhất cần sử dụng
để thực hiện bước 1 của chiến dịch.
Ví dụ:
ATTACK.INP
|
ATTACK.OUT
|
7 8
1 1 1 2 2 3 3
1 2
2 3
1 7
2 6
6 7
2 4
4 5
3 5
|
4
|
