VOI2011 NÂNG CẤP MẠNG

Nguồn: http://vn.spoj.com/problems/UPGRANET/

Một hệ thống gồm n máy tính đánh số từ 1 đến n được kết nối thành một mạng bởi m đoạn cáp mạng đánh số từ 1 đến m. Đoạn cáp mạng thứ i có thông lượng w_i kết nối hai máy u_i, v_icho phép truyền dữ liệu theo cả hai chiều giữa hai máy này.

Một dãy các máy x₁, x₂, …, x_p trong đó giữa hai máy x_j và x_j+1 (j = 1, 2, …, p-1) có đoạn cáp nối được gọi là một đường truyền tin từ máy x₁ tới máy x_p. Thông lượng của đường truyền tin được xác định như là thông lượng nhỏ nhất trong số các thông lượng của các đoạn cáp mạng trên đường truyền. Giả thiết là mạng được kết nối sao cho có đường truyền tin giữa hai máy bất kì và giữa hai máy có không quá một đoạn cáp mạng nối chúng.

Người ta muốn nâng cấp mạng bằng cách tăng thông lượng của một số đoạn cáp nối trong mạng. Để tăng thông lượng của mỗi đoạn cáp mạng thêm một lượng d (d > 0) ta phải trả một chi phí đúng bằng d. Việc nâng cấp mạng phải đảm bảo là sau khi hoàn tất, thông lượng của mỗi đoạn cáp mạng i đều bằng thông lượng của đường truyền tin có thông lượng lớn nhất từ máy u_i tới máy v_i.

Yêu cầu: Tìm phương án nâng cấp các đoạn cáp mạng sao cho tổng chi phí nâng cấp là nhỏ nhất.

Dữ liệu vào: Từ tệp văn bản UPGRANET.INP

·         Dòng thứ nhất: Chứa hai số nguyên dương n, m (n, m <= 10^5).

·         Dòng thứ i trong số m dòng tiếp theo chứa ba số nguyên dương u_i, v_i, w_i (w_i <= 10^6),
i = 1, 2, …, m.

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Kết quả: ghi ra tệp văn bản UPGRANET.OUT một số nguyên duy nhất là tổng chi phí nâng cấp theo phương án tìm được.

Ví dụ:

UPGRANET.INP	UPGRANET.OUT
6 7 1 2 6 1 3 5 2 4 3 3 4 9 4 5 4 4 6 8 5 6 7	5

Giới hạn: 50% số test tương ứng với 50% số điểm có N<=100;

SOLUTION  - CODE

LỊCH MỚI

Các nhà bác học xứ Byteland tranh luận với nhau rất nhiều về cách xây dựng lịch phù hợp với hành tinh của mình, trong đó quan trọng nhất là xác định năm nhuận. Ở đại hội lần thứ XII có một phương pháp xác định năm nhuận hoàn toàn mới được mọi người hết sức chú ý.

Theo cách tính này, số năm được xét dưới dạng nhị phân (không có các số 0 không có nghĩa ở đầu) .Các số giống nhau đứng liên tiếp tạo thành một nhóm. Nếu số chứa đúng 3 nhóm thì đó là năm nhuận. Ví dụ các năm 9 = 1001₂ và 13 = 1101₂ là năm nhuận, còn 7 = 111₂ – không phải là nhuận. Năm được đánh số từ 1 trở đi một cách liên tiếp.

Người ta muốn kiểm nghiệm độ chính xác của lịch này và tính số lượng năm nhuận trong khoảng thời gian từ a đến b (kể cả a và b).

Hãy xác định số năm nhuận trong khoảng đã cho.

Dữ liệu: Vào từ file văn bản CALENDAR.INP: gồm một dòng chứa 2 số nguyên a và b (1 ≤ a ≤ b ≤ 10¹⁸).

Kết quả: Đưa ra file văn bản CALENDAR.OUT một số nguyên – số năm nhuận.

Ví dụ:

CALENDAR.INP	CALENDAR.OUT
19 30	5

SOLUTION - TEST - CODE