Đề thi thử Quốc gia 2016 - 2017 (Pre VNOI) - ngày 2  (Bấm vào liên kết phía dưới để tải xuống)

Mời các bạn tham khảo đề ngày 2 kì thi thử Quốc gia môn Tin học, năm học 2016 - 2017. Kì thi vừa diễn ra tại trường chuyên Trần Phú - Hải Phòng ngày 27/11/2016

Đề thi thử Quốc gia 2016 - 2017 (Pre VNOI) - ngày 2

Hay lâp ̣ trinh giai cac bai toan sau đây:
̃ 4. SIMPLEGRAPH
GS. PVH có một đồ thị vô hướng liên thông gồm N đỉnh và M cạnh. Mỗi cạnh có một độ dài nguyên dương khác nhau. Giữa hai đỉnh bất kỳ có thể chứa nhiều cạnh nối, và có thể có những cạnh nối từ một đỉnh tới chính nó. Có P cặp đỉnh quan trọng trên đồ thị. GS. cần tô màu các cạnh thành một trong hai màu cam và tím, sao cho với mọi cặp đỉnh quan trọng (u, v), mọi đường đi ngắn nhất từ u đến v đều chứa một số lẻ các cạnh màu cam.
INPUT
- Dòng đầu tiên chứa số nguyên T - số hiệu của subtask chứa test này.
Chú ý: T không phải là số lượng bộ dữ liệu. Mỗi file input có duy nhất một bộ dữ liệu.T chỉ giúp bạn dễ dàng nhận biết một test thuộc subtask nào hay thôi.
- Dòng thứ hai chứa ba số nguyên N, M, P lần lượt là số đỉnh, số cạnh và số cặp đỉnh quan trọng trên đồ thị.
- M dòng tiếp theo, mỗi dòng chứa ba số nguyên u, v, c, thể hiện một cạnh độ dài c nối giữa hai đỉnh u và v.
- P dòng tiếp theo, mỗi dòng chứa hai số nguyên u và v thể hiện một cặp đỉnh quan trọng.
Nhắc lại, dữ liệu vào không đảm bảo đồ thị đã cho là đơn đồ thị, nghĩa là có thể tồn tại nhiều cạnh nối cùng một cặp đỉnh, hoặc một cạnh nối một đỉnh tới chính nó.
OUTPUT
- Dòng đầu tiên in ra “NO” nếu không tồn tại cách tô màu thỏa mãn, hoặc “YES” nếu ngược lại.
- Nếu dòng đầu in ra YES, in ra thêm M dòng, dòng thứ i gồm một trong hai xâu ký tự “ORANGE” hoặc “PURPLE” thể hiện màu của cạnh thứ i. Các cạnh được đánh số từ 1 tới M, theo thứ tự xuất hiện trong file input. Nếu có nhiều hơn một cách tô màu thỏa mãn, bạn được quyền in ra một cách bất kỳ.

GIẢI THÍCH
Có duy nhất một đường đi ngắn nhất từ 2 đến 6 (2 → 5 → 6, độ dài 14). Đường đi này có một cạnh màu cam (2 → 5).
Có duy nhất một đường đi ngắn nhất từ 7 đến 3 (7 → 2 → 3, độ dài 18). Đường đi này có một cạnh màu cam (7 → 2).
Có duy nhất một đường đi ngắn nhất từ 1 đến 2 (1 → 5 → 2, độ dài 15). Đường đi này có một cạnh màu cam (5 → 2).
Có duy nhất một đường đi ngắn nhất từ 3 đến 6 (3 → 2 → 5 → 6, độ dài 24). Đường đi này có một cạnh màu cam (2 → 5).
Có duy nhất một đường đi ngắn nhất từ 4 đến 7 (4 → 1 → 5 → 2 → 7, độ dài 30). Đường đi này có ba cạnh màu cam (4 → 1, 5 → 2 và 2 → 7).
Cách tô màu “PURPLE ORANGE PURPLE ORANGE ORANGE ORANGE” cũng hợp lệ với giải thích tương tự, nhưng cách tô màu “PURPLE ORANGE ORANGE ORANGE ORANGE ORANGE” không hợp lệ vì đường đi 2 → 5 → 6 chứa hai cạnh màu cam, là số chẵn. 

Tải xuống để xem tài liệu hoàn chỉnh - Chia sẻ cho bạn bè nếu trang web có ích với bạn!
Nguồn tài liệu:

Bạn cũng có thể quan tâm:

Bài tập môn Tin học lớp Lớp 12
Mời bạn tham gia hỏi - đáp
Thư viện bài tập © 2014 -2017 - Liên hệ - Giới thiệu - Bản quyền - Chính sách bảo mật - Sitemap