MẠNG TRUYỀN THÔNG

Nguồn: Đề thi học sinh giỏi quốc gia 2013

Tổng công ty Z gồm N công ty con, đánh số từ 1-N. Mỗi công ty con có một máy chủ. Để đảm bảo truyền tin giữa các công ty, Z thuê M đường truyền tin để kết nối N máy chủ thành một mạng máy tính của Tổng công ty. Không có 2 đường truyền nối cùng 1 cặp máy chủ. Đường truyền i nối máy chủ của 2 công ty u_i, v_i có chi phí là w_i. Mạng máy tính có tính thông suốt, nghĩa là từ một máy chủ có thể truyền tin đến một máy chủ bất kì khác bằng đường truyền trực tiếp hoặc qua nhiều đường trung gian.

Một đường truyền gọi là không tiềm năng nếu như : một mặt, việc loại bỏ đường truyền này không làm mất tính thông suốt; mặt khác, nó phải có tính không tiềm năng, nghĩa là không thuộc bất cứ mạng con thông suốt gồm N máy chủ và N-1 đường truyền tin với tổng chi phí thuê bao nhỏ nhất nào của mạng máy tính.

Trong thời gian tới, chi phí thuê bao của một số đường truyền tin thay đổi. Tổng công ty muốn xác định với chi phí mới thì đường truyền thứ k có là đường không tiềm năng hay không để xem xét chấm dứt việc thuê đường truyền này.

Yêu cầu: Cho Q giả định, mỗi giả định cho biết danh sách các đường truyền tin với chi phí thuê mới và chỉ số k. Với mỗi giả định về chi phí mới thuê đường truyền tin, hãy xác định đường truyền tin thứ k có là đường truyền tin không tiềm năng trong mạng không.

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

+ Dòng đầu là T – số testcase. T nhóm dòng, mỗi nhóm cho thông tin về một testcase.

+ Dòng thứ nhất gồm 3 số nguyên dương N, M, Q (Q <= 30).

+ Dòng thứ i trong M dòng tiếp theo chứa 3 số nguyên dương u_i, v_i, w_i (u_i ≠ v_i, w_i < 10⁹).

+ Dòng thứ j trong Q dòng tiếp theo mô tả giả định thứ j:

- Số đầu tiên là chỉ số k_j của đường truyền tin cần xem xét

- Tiếp theo là s_j ( s_j <= 100) cho biết số lượng đường truyền có chi phí thuê mới

- Cuối cùng là s_j cặp số nguyên dương t_p, c_p cho biết đường truyền thứ t_p có chi phí thuê mới là c_p (c_p < 10⁹).

Dữ liệu ra: ghi vào tệp văn bản COMNET.OUT

+ Gồm T nhóm dòng, mỗi nhóm gồm Q dòng. Mỗi dòng là câu trả lời cho giả định tương ứng trong input. Ghi YES nếu câu trả lời là khẳng định và NO trong trường hợp ngược lại.

Ví dụ:

COMNET.INP	COMNET.OUT
1 3 3 2 1 2 1 1 3 2 2 3 3 3 2 2 4 3 4 1 1 1 4	NO YES

Giới hạn

+ 30% số test đầu có 1 ≤ N ≤ 100;

+ 30% số test tiếp theo có 1 ≤ N ≤ 10⁴ và 1 ≤ M ≤ 10⁵;

+ 40% số test còn lại có 1 ≤ N ≤ 10⁵ và 1 ≤ M ≤ 10⁶.

SOLUTION - TEST - CODE

MẠNG RÚT GỌN

Một hệ thống gồm N máy tính được nối thành một mạng có M kênh nối, mỗi kênh nối hai máy tính trong mạng, giữa hai máy tính có không quá một kênh nối. Các máy tính được đánh số từ 1 đến N, các kênh nối đánh số từ 1 đến M. Việc truyền tin trực tiếp có thể thực hiện được đối với hai máy có kênh nối. Các kênh nối trong mạng được chia thành ba loại 1, 2 và 3. Ta nói giữa hai máy a và b trong mạng  có đường truyền tin loại k (k=1 hoặc k=2) nếu tìm được dãy các máy (a=v₁, v₂,…,v_p=b) thoả mãn điều kiện: giữa hai máy v_i và v_i+1 hoặc có kênh nối loại k hoặc có kênh nối loại 3 (i=1, 2,..., p-1).

Yêu cầu: Cần tìm cách loại bỏ khỏi mạng một số nhiều nhất kênh nối nhưng vẫn đảm bảo luôn tìm được cả đường truyền loại 1 lẫn đường truyền tin loại 2 giữa hai máy bất kỳ trong mạng.

Dữ liệu vào: từ tệp văn bản RUTGON.INP như sau:

+ Dòng đầu tiên chứa hai số N, M (N≤500); M≤10000).

+ Dòng thứ i trong M dòng tiếp theo chứa ba số nguyên dương u, v, s cho biết kênh thứ i nối hai máy u và v thuộc loại s.

Dữ liệu ra: ghi vào tệp văn bản RUTGON.OUT gồm:

Dòng đầu tiên ghi số r là số kênh cần loại bỏ.

+ Nếu  r=-1 thì có nghĩa là trong mạng đã cho tồn tại hai máy không có đường truyền loại 1 hoặc loại 2.

+ Nếu r=0 có nghĩa là mạng có đường truyền thoả mãn nhưng số kênh loại bỏ bằng 0.

+ Nếu r>0 thì r dòng tiếp theo, mỗi dòng ghi chỉ số của một kênh cần loại bỏ.

Các số trên cùng một dòng của các tệp dữ liệu và tệp kết quả cách nhau ít nhất một dấu cách.

Ví dụ:

RUTGON.INP	RUTGON.OUT
5 7 1 2 3 2 3 3 3 4 2 5 3 2 5 4 1 5 2 2 1 5 1	2 6 7

NỐI DÂY

Cho một lưới ô vuông trên mặt phẳng với hệ tọa độ trực chuẩn có một cạnh nằm trên tia Ox và một cạnh nằm trên tia Oy. Trên lưới người ta đặt n đèn ở các điểm có tọa độ nguyên và điền số 0 vào tất cả các ô của lưới . Hai bóng đèn được nối với nhau bằng dây dẫn, dây dẫn luôn là một đoạn thẳng nối hai đèn và tất cả các ô trong các ô vuông có điểm trong chung với dây dẫn được tăng lên một đơn vị.

Hệ thống đèn chỉ hoạt động nếu hai bóng đèn bất kỳ luôn được nối với nhau (trực tiếp hoặc thông qua một số bóng đèn trung gian)

Yêu cầu: Nối các dây dẫn cho hệ thống hoạt động sao cho khi hoàn thành, tổng các số ghi trên các ô của lưới là nhỏ nhất có thể.

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

+ Dòng đầu chứa số nguyên dương n ≤ 1000

+ n dòng tiếp theo, mỗi dòng chứa hoành độ và tung độ một đèn, tọa độ là số tự nhiên có giá rị không quá 10⁹. Các đèn luôn đảm bảo nằm trong lưới.

Kết quả: ghi ra tệp văn bản WIRES.OUT

+ Dòng 1 ghi tổng các số trên các ô vuông của lưới theo phương án tìm được.

+ Các dòng tiếp theo, mỗi dòng ghi 2 chỉ số của 2 đèn được nối với nhau bằng dây dẫn

Ví dụ:

WIRES.INP	WIRES.OUT
5 0 1 1 4 2 2 3 0 4 3	8 1 3 2 3 4 3 5 3

TEST -  SOLUTION - CODE

Thuật toán Bellman - Ford

NỐI DÂY

Cho hai đường thẳng song song nằm ngang a và b. Trên mỗi đường thẳng, người ta chọn lấy n điểm phân biệt và gán cho mỗi điểm một số nguyên dương là nhãn của điểm đó:

+ Trên đường thẳng a, điểm thứ i (theo thứ tự từ trái qua phải) được gán nhãn là a_i.

+ Trên đường thẳng b, điểm thứ j (Theo thứ tự từ trái qua phải) được gán nhãn là b_j.

Ở đây (a₁, a₂,…,a_n) và (b₁, b₂,…,b_n) là những hoán vị của dãy số (1, 2,…,n)

Yêu cầu: Hãy chỉ ra một số tối đa các đoạn thẳng thỏa mãn:

+ Mỗi đoạn thẳng phải nối hai điểm có cùng một nhãn: Một điểm trên đường thẳng a và một điểm trên đường thẳng b.

+ Các đoạn thẳng đôi một không có điểm chung

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

+ Dòng 1: chứa số nguyên dương n ≤ 10⁵

+ Dòng 2: chứa n số theo thứ tự là a₁, a₂,…,a_n

+ Dòng 3: Chứa n số theo thứ tự là b₁, b₂,…,b_n

Kết quả: Ghi ra tệp văn bản LINES.OUT

+ Dòng 1: ghi số k là số đoạn thẳng nối được.

+ Dòng 2: Ghi k nhãn của các đoạn thẳng được chọn (nhãn của mỗi đoạn thẳng là nhãn của điểm đầu mút)

Các số trên một dòng trong tệp input/output được/phải ghi cách nhau ít nhất một ký tự trắng.

Ví dụ:

LINES.INP	LINES.OUT
6 2 3 1 5 6 4 3 2 5 6 1 4	4 3 4 5 6

 TEST -  CODE