Trên thực tế có nhiều bài toán liên quan tới một tập các đối tượng và những mối liên hệ giữa chúng, đòi hỏi toán học phải đặt ra một mô hình biểu diễn một cách chặt chẽ và tổng quát bằng ngôn ngữ ký hiệu, đó là đồ thị
Các bài toán đồ thị trong các kỳ thi Quốc gia
tải về 418.79 Kb.
|
- Điều hướng trang này:
- NHP.INP NHP.OUT
- QUANTUONG.INP QUANTUONG.OUT
- Kênh xung yếu (2006 – vòng 1)
- Ví dụ: XUNGYEU.INP
- Hạn chế: Trong tất cả các test: n ≤ 1000, m ≤ 20000. Có 50% số lượng test với n ≤ 200. Robot cứu hỏa (2007 - vòng 1)
- Nút st - xung yếu (2009 – vòng 1)
8. Các bài toán đồ thị trong các kỳ thi Quốc gia
Một hệ thống n máy tính (các máy tính được đánh số từ 1 đến n) được nối lại thành một mạng bởi m kênh nối, mỗi kênh nối hai máy nào đó và cho phép ta truyền tin một chiều từ máy này đến máy kia. Giả sử s và t là 2 máy tính trong mạng. Ta gọi đường truyền từ máy s đến máy t là một dãy các máy tính và các kênh nối chúng có dạng: s = u1, e1, u2, ..., ui, ei, ui+1, ..., uk-1, ek-1, uk = t trong đó u1, u2, ..., uk là các máy tính trong mạng, ei - kênh truyền tin từ máy ui đến máy ui+1. (i = 1, 2,... , k-1). Mạng máy tính được gọi là thông suốt nếu như đối với hai máy u, v bất kỳ ta luôn có đường truyền tin từ u đến v và đường truyền tin từ v đến u. Mạng máy tính được gọi là hầu như thông suốt nếu đối với hai máy u, v bất kỳ, hoặc là có đường truyền từ u đến v, hoặc là có đường truyền từ v đến u. Biết rằng mạng máy tính đã cho là hầu như thông suốt nhưng không thông suốt. Yêu cầu: hãy xác định xem có thể bổ sung đúng một kênh truyền tin để biến mạng đã cho trở thành thông suốt được không? Dữ liệu
Các số trên cùng một dòng được ghi cách nhau bởi dấu cách. Kết qủa
Hạn chế Trong tất cả các test, n ≤ 2000, m ≤ 30000. Ví dụ
Xét bàn cờ vuông kích thước n×n. Các dòng được đánh số từ 1 đến n, từ dưới lên trên. Các cột được đánh số từ 1 đến n từ trái qua phải. Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Trên bàn cờ có m (0 ≤ m ≤ n) quân cờ. Với m > 0, quân cờ thứ i ở ô (ri, ci), i = 1,2,..., m. Không có hai quân cờ nào ở trên cùng một ô. Trong số các ô còn lại của bàn cờ, tại ô (p, q) có một quân tượng. Mỗi một nước đi, từ vị trí đang đứng quân tượng chỉ có thể di chuyển đến được những ô trên cùng đường chéo với nó mà trên đường đi không phải qua các ô đã có quân 
Cần phải đưa quân tượng từ ô xuất phát (p, q) về ô đích (s,t). Giả thiết là ở ô đích không có quân cờ. Nếu ngoài quân tượng không có quân nào khác trên bàn cờ thì chỉ có 2 trường hợp: hoặc là không thể tới được ô đích, hoặc là tới được sau không quá 2 nước đi (hình trái). Khi trên bàn cờ còn có các quân cờ khác, vấn đề sẽ không còn đơn giản như vậy. Yêu cầu: Cho kích thước bàn cờ n, số quân cờ hiện có trên bàn cờ m và vị trí của chúng, ô xuất phát và ô đích của quân tượng. Hãy xác định số nước đi ít nhất cần thực hiện để đưa quân tượng về ô đích hoặc đưa ra số -1 nếu điều này không thể thực hiện được. Dữ liệu vào: Dòng đầu tiên chứa 6 số nguyên n, m, p, q, s, t. Nếu m > 0 thì mỗi dòng thứ i trong m dòng tiếp theo chứa một cặp số nguyên ri , ci xác định vị trí quân thứ i. Hai số liên tiếp 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ả ra: Gồm 1 dòng duy nhất là số nước đi tìm được Ví dụ:
Hạn chế:Trong tất cả các test: 1 ≤ n ≤ 200. Có 60% số lượng test với n ≤ 20.
Một hệ thống n máy tính (các máy tính được đánh số từ 1 đến n) được nối lại thành một mạng bởi m kênh nối, mỗi kênh nối hai máy nào đó và cho phép truyền tin một chiều từ máy này đến máy kia. Ta gọi một mạch vòng của mạng đã cho là một dãy các máy tính và các kênh nối chúng có dạng: u1, e1, u2, ...,ui, ei, ui+1, ..., uk-1, ek-1, uk, ek, u1 Trong đó u1, u2, ..., uk là các máy tính khác nhau trong mạng, ei – kênh truyền tin từ máy ui đến máy ui+1 (i = 1, 2, ..., k-1), ek là kênh truyền tin từ máy uk đến máy u1. Một kênh truyền tin trong mạng được gọi là kênh xung yếu nếu như bất cứ mạch vòng nào của mạng cũng đều chứa nó.
InputDòng đầu tiên chứa 2 số nguyên dương n và m. Dòng thứ i trong số m dòng tiếp theo mô tả kênh nối thứ i bao gồm hai số nguyên dương ui, vi cho biết kênh nối thứ i cho phép truyền tin từ máy ui đến máy vi. Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.
OutputDòng đầu tiên ghi số nguyên k là số lượng kênh xung yếu trong mạng đã cho. Ghi k = -1 nếu mạng không chứa kênh xung yếu. Nếu k>0 thì mỗi dòng trong số k dòng tiếp theo ghi thông tin về một kênh xung yếu tìm được theo qui cách mô tả giống như trong file dữ liệu vào. Đồng thời các kênh được in ra theo thứ tự từ điển Ví dụ:
Hạn chế:Trong tất cả các test: n ≤ 1000, m ≤ 20000. Có 50% số lượng test với n ≤ 200.
Trên một mạng lưới giao thông có n nút, các nút được đánh số từ 1 đến n và giữa hai nút bất kỳ có không quá một đường nối trực tiếp (đường nối trực tiếp là một đường hai chiều). Ta gọi đường đi từ nút s đến nút t là một dãy các nút và các đường nối trực tiếp có dạng: s = u1, e1, u2,..., ui, ei, ui+1, ..., uk-1, ek-1, uk = t, trong đó u1, u2, …, uk là các nút trong mạng lưới giao thông, ei là đường nối trực tiếp giữa nút ui và ui+1 (không có nút uj nào xuất hiện nhiều hơn một lần trong dãy trên, j = 1, 2, …, k). Biết rằng mạng lưới giao thông được xét luôn có ít nhất một đường đi từ nút 1 đến nút n. Một robot chứa đầy bình với w đơn vị năng lượng, cần đi từ trạm cứu hoả đặt tại nút 1 đến nơi xảy ra hoả hoạn ở nút n, trong thời gian ít nhất có thể. Thời gian và chi phí năng lượng để robot đi trên đường nối trực tiếp từ nút i đến nút j tương ứng là tij và cij (1 ≤ i, j ≤ n). Robot chỉ có thể đi được trên đường nối trực tiếp từ nút i đến nút j nếu năng lượng còn lại trong bình chứa không ít hơn cij (1 ≤ i, j ≤ n). Nếu robot đi đến một nút có trạm tiếp năng lượng (một nút có thể có hoặc không có trạm tiếp năng lượng) thì nó tự động được nạp đầy năng lượng vào bình chứa với thời gian nạp coi như không đáng kể. Yêu cầu: Hãy xác định giá trị w nhỏ nhất để robot đi được trên một đường đi từ nút 1 đến nút n trong thời gian ít nhất. Input Dòng đầu tiên chứa một số nguyên dương n (2 ≤ n ≤ 500); Dòng thứ hai chứa n số, trong đó số thứ j bằng 1 hoặc 0 tương ứng ở nút j có hoặc không có trạm tiếp năng lượng (j = 1, 2, …, n); Dòng thứ ba chứa số nguyên dương m (m ≤ 30000) là số đường nối trực tiếp có trong mạng lưới giao thông; Dòng thứ k trong số m dòng tiếp theo chứa 4 số nguyên dương i, j, tij, cij (tij, cij ≤ 10000) mô tả đường nối trực tiếp từ nút i đến nút j, thời gian và chi phí năng lượng tương ứng. Hai số liên tiếp trên một dòng trong file dữ liệu cách nhau ít nhất một dấu cách. Output Ghi ra số nguyên dương w tìm được. V 
Output: 3 í dụ:
Nhảy lò cò là trò chơi dân gian của Việt Nam. Người trên hành tinh X cũng rất thích trò chơi này và họ đã cải biên trò chơi này như sau: Trên mặt phẳng vẽ n vòng tròn được đánh số từ 1 đến n. Tại vòng tròn i người ta điền số nguyên dương ai. Hai số trên hai vòng tròn tùy ý không nhất thiết phải khác nhau. Tiếp đến người ta vẽ các mũi tên, mỗi mũi tên hướng từ một vòng tròn đến một vòng tròn khác. Quy tắc vẽ mũi tên là: Nếu có ba số ai, aj, ak thỏa mãn ak = ai + aj thì vẽ mũi tên hướng từ vòng tròn i đến vòng tròn k và mũi tên hướng từ vòng tròn j đến vòng tròn k. Người chơi chỉ được di chuyển từ một vòng tròn đến một vòng tròn khác nếu có mũi tên xuất phát từ một trong số các vòng tròn, di chyển theo cách mũi tên đã vẽ để đi đến các vòng tròn khác. Người thắng cuộc sẽ là người tìm được cách di chuyển qua nhiều vòng tròn nhất. Ví dụ: Với 5 vòng tròn và các số trong vòng tròn là 1, 2, 8, 3, 5, trò chơi được trình bày trong hình dưới đây: 
Khi đó có thể di chuyển được nhiều nhất qua 4 vòng tròn (tương ứng với đường di chuyển được tô đậm trên hình vẽ). Yêu cầu Hãy xác định xem trong trò chơi mô tả ở trên, nhiều nhất có thể di chuyển được qua bao nhiêu vòng tròn. Dữ liệu
Hai số liên tiếp trên một dòng được ghi cách nhau bởi dấu cách. Kết quả Ghi ra số lượng vòng tròn trên đường di chuyển tìm được. Ràng buộc
Ví dụ D Kết qủa 4
ữ liệu: 5 1 2 8 3 5
Bản đồ giao thông của hành tinh X bao gồm n thành phố được đánh số từ 1 đến n và m đoạn đường một chiều nối các cặp thành phố, giữa hai thành phố bất kỳ có không quá một đoạn đường cùng chiều nối chúng. Thành phố s là thủ đô của hành tinh, từ đó có thể di chuyển theo các đoạn đường nối giữa các thành phố để đến bất cứ thành phố nào trong số các thành phố còn lại. Thành phố t là một điểm du lịch ưa thích của người dân thủ đô. Hàng năm có một lượng lớn người dân thủ đô đến nghỉ ngơi tại điểm du lịch hấp dẫn này. Vì thế, trong các mùa du lịch ách tắc giao thông trên đường đi từ s đến t thường xuyên xảy ra tại một số nút giao thông. Do đó, Bộ Giao thông của hành tinh X muốn xác định các nút giao thông này. Ta nói thành phố a ( a ≠ s và a ≠ t) là nút st-xung yếu nếu mọi đường đi từ s đến t đều phải đi qua a. Yêu cầu: Hãy xác định số lượng các nút st-xung yếu. Dữ liệu:
Kết quả
Ví dụ 
Ràng buộc: 60% số tests ứng với 60% số điểm của bài có 3 ≤ n ≤ 100.
Trong mạng xã hội, mỗi trang web được tổ chức trên một máy tính thành viên và cung cấp dịch vụ truy nhập tới một số trang web khác. Để truy nhập tới một trang web nào đó không có trong danh mục kết nối trực tiếp của mình, người dùng phải truy nhập tới trang web khác có kết nối với mình, dựa vào danh mục dịch vụ của trang web này để chuyển tới trang web khác theo tùy chọn, cứ như thế cho đến khi tới được trang web mình cần. Thời gian để truy nhập tới một trang web phụ thuộc chủ yếu và số lần mở trang web trong quá trình truy nhập. Như vậy, người dùng cần chủ động chọn lộ trình truy nhập hợp lí. Sau một thời gian làm việc trên mạng, Sáng - một thành viên nhiệt thành đã tích lũy kinh nghiệm, tạo một cơ sở dữ liệu, cho biết từ một trang web có thể đi tới những trang web nào trong mạng. Trong cơ sở dữ liệu, các trang web được đánh số từ 1 đến n và có m bản ghi, mỗi bản ghi có dạng cặp có thứ tự (u, v) cho biết trang web u có kết nối tới trang web v ( 1 ≤ u, v ≤ n, u ≠ v). Cơ sở dữ liệu chưa được chuẩn hóa, vì vậy có thể chứa các cặp (u, v) giống nhau. Trang web của Sáng có số hiệu là s. Dựa vào cơ sở dữ liệu, Sáng có thể xác định lộ trình truy nhập nhanh nhất (tức là số lần phải mở trang web là ít nhất) từ trang web s tới trang web u bất kì. Tuy vậy, ở mạng xã hội, mọi chuyện đều có thể xảy ra: một khu vực nào đó bị mất điện, máy của một thành viên bị hỏng, trang web đó đang bị đóng để nâng cấp, ... Kết quả là một vài trang web nào đó có thể tạm thời không hoạt động. Như vậy, nếu từ s có ít nhất hai lộ trình nhanh nhất khác nhau tới u thì khả năng thực hiện truy nhập được một cách nhanh nhất tới u là lớn hơn so với những trang web chỉ có duy nhất một lộ trình nhanh nhất. Hai lộ trình gọi là khác nhau nếu có ít nhất một trang web có ở lộ trình này mà không có ở lộ trình kia hoặc cả hai lộ trình cùng đi qua những trang web như nhau nhưng theo các trình tự khác nhau. Những trang web mà từ s tới đó có ít ra là hai lộ trình nhanh nhất khác nhau được gọi là ổn định đối với s. Trang web mà từ s không có lộ trình tới nó là không ổn định đối với s.
Ví dụ, với mạng nêu ở hình trên (n = 6, m = 9) các trang web 4 và 3 là ổn định với s = 1 (từ 1 tới 4 có 2 lộ trình nhanh nhất: 1 - 2 - 4 và 1 - 5 - 4, từ 1 tới 3 cũng có 2 lộ trình nhanh nhất: 1 - 2 - 4 - 3 và 1 - 5 - 4 - 3). Каталог: forum -> attachment forum -> Kiểm tra kiến thức Sinh học lớp 12 forum -> Danh sách giao lưu đại học Sookmyung ( 8/1/2014) Lớp 4H12 attachment -> CHƯƠng I: LẮp ráp và CÀI ĐẶt máy tíNH attachment -> BÀi tập lớn môn: Kiến trúc máy tính Yêu cầu: Tìm hiểu kiến trúc mips attachment -> BÀI 1 : html cơ sở 1-Thành phần-Element tải về 418.79 Kb. Chia sẻ với bạn bè của bạn:
|
