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ị

Chuyên đề: LUỒNG TRÊN MẠNG

1. Luồng cực đại trên mạng

Mã bài: NKFLOW

Mô hình các ống dẫn nước bằng một mạng luồng. Mỗi ống nước có đường kính xác định nên chỉ cho phép một lưu lượng nước xác định chảy qua. Ở nơi giao điểm giữa các ống, lưu lượng nước đi vào phải bằng lưu lượng nước đi ra nếu không nước sẽ nhanh chóng bị thất thoát. Ta có một bồn nước, hay đỉnh phát, và một vòi nước, hay đỉnh thu. Một cách trực quan, giá trị luồng trên mạng chính là vận tốc nước chảy ra từ vòi. Luồng còn có thể mô hình sự lưu chuyển của người hay hàng hóa trên các mạng giao thông, dòng điện trong hệ thống phân phối,... Đối với các hệ thống mạng này, luồng đi vào các nút trung gian cần phải bằng luồng đi ra khỏi nút đó. Tính chất này cũng giống như định luật dòng điện Kirchhoff. Mạng luồng còn được ứng dụng trong sinh thái học: mạng luồng xuất hiện khi xem xét sự lưu chuyển chất dinh dưỡng và năng lượng giữa các nhóm khác nhau trong một mạng thức ăn. Các bài toán gắn với loại mạng sinh thái này hoàn toán khác với trường hợp mạng chất lỏng hay mạng giao thông.

Bài toán luồng cực đại trên mạng yêu cầu tìm một luồng tương thích có giá trị lớn nhất trong mạng luồng có một đỉnh phát và một đỉnh thu. Bài toán luồng cực đại trên mạng có thể xem như trường hợp đặc biệt của lớp các bài toán mạng phức tạp hơn, chẳng hạng như bài toán lưu thông. Định lý luồng cực đại-lát cắt hẹp nhất (max-flow min-cut theorem) chỉ ra giá trị luồng cực đại từ s đến t (đỉnh phát đến đỉnh thu) bằng giá trị của lát cắt s-t hẹp nhất trên mạng.

Bạn hãy thử giải quyết bài toán luồng cực đại trên mạng: cho một mạng luồng, hãy tìm giá trị luồng cực đại.

Dữ liệu

• 
  Dòng đầu tiên chứa 4 số nguyên dương n, m, s, t, (2 ≤ n ≤ 1000) tương ứng là số đỉnh, số cạnh của đồ thị, chỉ số của đỉnh phát và đỉnh thu.
  
• 
  m dòng tiếp theo, mỗi dòng có dạng ba số u, v, c cách nhau ít nhất một dấu cách thể hiện có cung u, v trong mạng với khả năng thông qua là c (1 ≤ c ≤ 10⁶).
  

Kết qủa

Ví dụ

6 8 1 6

1 3 5

2 5 3

3 5 1

5 6 6
Kết qủa

9

Bảo vệ

Mã bài: BAOVE

Input

Output

Ví dụ

Example

2. Báo động đỏ

Mã bài: ALERT

Thế giới những năm 2077 hình thành nên 2 thái cực rõ ràng , các nước hoặc là đi theo con đường Chủ Nghĩa Xã Hội hoặc là theo Tư Bản Chủ Nghĩa. Khởi xướng nên các luồng tư tưởng này là 2 nước Lào và Campuchia . Lào và 1 số nước thân Lào theo đường lối Xã Hội Chủ Nghĩa còn Campuchia và 1 số nước thân Campuchia theo Tư Bản Chủ Nghĩa. Như ta đã biết nền kinh tế các năm trong tương lai là nền kinh tế tri thức và của các mối quan hệ. Nếu trước đây 2 nước X và Y có quan hệ kinh tế là Z tỉ đôla với nhau và giờ X theo CNXH còn Y theo TBCN thì 2 nước này sẽ cắt đứt mối quan hệ kinh tế với nhau , đối với nền kinh tế thế giới thì thực sự là 1 tổn thất lớn , còn nếu 2 nước cùng đi theo cùng 1 con đường chính trị thì mối quan hệ đó vẫn được duy trì . Tuy nhiên năm nay mới là năm 2007 vì thế mới chỉ có Lào , các nước thân Lào là theo CNXH và Campuchia và các nước thân Campuchia theo TBCN , còn lại các nước vẫn theo con đường trung lập và tới năm 2077 họ mới chọn TBCN hay là XHCN.
Biết bạn rất giỏi lập trình , các chuyên gia thuộc Liên Hợp Quốc muốn nhờ bạn hãy lập trình tính xem tới năm 2077 thì trong tình huống tốt nhất thì Tổng Giá Trị Kinh Tế Toàn Cầu là bao nhiêu ? Biết rằng Tổng Giá Trị Kinh Tế Toàn Cầu được tính bằng tổng giá trị các mối quan hệ kinh tế giữa các nước trên thế giới .

Input

Dòng 1 : Số nguyên dương N ( 1 ≤ N ≤ 200 ) là số lượng các quốc gia trên thế giới , các quốc gia được đánh số thứ tự từ 1 -> N .
Dòng 2 : Số nguyên dương L là các nước tính tới thời điểm hiện tại đang theo CNXH .
Dòng 3 : Gồm L số nguyên dương là chỉ số của các nước đang theo CNXH .
Dòng 4 : Số nguyên dương C là các nước tính tới thời điểm hiện tại đang theo TBCN.
Dòng 5 : Gồm C số nguyên dương là chỉ số của các nước đang theo TBCN .
Dòng 6 : Số nguyên dương M ( 1 ≤ M ≤ N*(N-1)/2 ) là số quan hệ kinh tế giữa các nước trên thế giới .
M dòng tiếp theo , dòng thứ i gồm 3 số nguyên dương Xi Yi Zi ( 1 ≤ Xi ≠ Yi ≤ N , 1 ≤ Zi ≤ 1000 ) mô tả 1 mối quan hệ kinh tế .

Output

Dòng 1 : Số nguyên dương K là Tổng Giá Trị Kinh Tế Toàn Cầu trong tình huống tốt nhất và số nguyên dương T là số nước theo XHCN trong tình huống đó .
Dòng 2 : Ghi ra chỉ số của T nước theo CNXH trong tình huống tốt nhất đó. Nếu có nhiều phương án thì chỉ ra phương án mà có số lượng nước theo CNXH là nhiều nhất .

Ví dụ:

ALERT.INP	ALERT.OUT
3 1 1 1 3 1 1 2 10	10 2 1 2

3. Monkey island

Mã bài: NKTRAFIC

Sau khi phân chia đất nước thành các thành phố, đảo khỉ lại nảy sinh vấn đề mới: phải ngăn chặn việc vận chuyển chuối! Đảo khí có N thành phố đánh số từ 1 đến N nối với nhau bởi M đường nối hai chiều. Giữa hai thành phố có nhiều nhất một con đường. Giữa hai thành phố bất kỳ có ít nhất một đường đi (tạo bởi một hoặc nhiều con đường). Đảo khỉ có hai thủ đô là thành phố 1 và thành phố N.

Gần đây, việc vận chuyển chuối giữa hai thủ đô tăng vọt. Để tấn công việc vận chuyển, tổng thống huy động G binh lính, mỗi binh lính có thể đặt tại vị trí bất kỳ trên một con đường, có thể gần thành phố tùy ý, nhưng không được nằm trong thành phố. Trong trường hợp có lệnh tấn công vào một trong hai thủ đô, tất cả binh lính phải di chuyển đến thủ đô đó. Các binh lính di chuyển với vận tốc không đổi. Thời gian cần thiết để huy động một cuộc tấn công như vậy bằng khoảng cách lớn nhất từ các binh lính đến một trong hai thủ đô.

Yêu cầu: xác định một cách bố trí các binh lính sao cho mọi đường đi từ thủ đô này đến thủ đô kia đều đi qua ít nhất một con đường có binh lính gác và thời gian huy động tấn công trong trường hợp xấu nhất là nhỏ nhất.

Dữ liệu

• 
  Dòng đầu tiên chứa 3 số nguyên N, M, G cách nhau bởi khoảng trắng.
  
• 
  Mỗi dòng trong số M dòng sau chứa 3 số nguyên a, b, c cách nhau bởi khoảng trắng, cho biết có một đường nối hai chiều giữa thành phố a và b với độ dài c.
  

Kết qủa

In ra một số nguyên duy nhất là thời gian nhỏ nhất để tất cả các binh lính có thể di chuyển đến một thủ đô, với đúng một chữ số thập phân. Nếu không có lời giải, in ra -1.

Giới hạn

• 
  2 < N < 155
  
• 
  2 < M < 5055
  
• 
  0 < độ dài của một con đường < 1024
  
• 
  2 < G < 4096
  

Ví dụ

NKTRAFIC.INP	NKTRAFIC .OUT
6 6 2 1 2 1 2 3 2 3 6 1 1 4 1 4 5 3 5 6 1	2.5

4. Hệ thống đèn

Mã bài: LIGHT

Khu vực đặt các bể xăng của một Tổng Công Ty Xăng Dầu có dạng một hình chữ nhật được chia thành m * n ô vuông. Các ô vuông được đánh tọa độ 1 -> m từ trên xuống, 1 -> n từ trái sang.
Tại k ô của lưới có đặt các bể xăng. Người ta cần xây dựng một hệ thống đèn pha chiếu sáng, mỗi đèn chỉ chiếu dọc theo hoặc là hàng hoặc là cột của lưới ô vuông sao cho mỗi bể chứa xăng phải được chiếu sáng bởi ít nhất một đèn pha chiếu dọc theo hàng hoặc cột chứa nó. Biết:
- ai là chi phí xây dựng đèn chiếu sáng dọc theo hàng.
- bj là chi phí xây dựng đèn chiếu sáng dọc theo cột.

Yêu cầu: Tìm cách xây dựng hệ thống đèn với tổng chi phí xây dựng là nhỏ nhất.

Input

-Dòng đầu tiên chứa 3 số nguyên dương m, n, k (m, n <= 100).
-Dòng thứ hai chứa m số nguyên a1, a2, ..., am.
-Dòng thứ ba chứa n số nguyên b1, b2, ..., bn.
- Dòng thứ i trong k dòng tiếp theo chứa tọa độ của bể xăng thứ i.

Output

Một dòng duy nhất ghi tổng chi phí theo cách xây dựng tìm được.

Ví dụ:

LIGHT.INP	LIGHT.OUT
2 3 4 15 17 2 4 6 1 1 2 2 2 3 2 1	12

5. Luồng với chi phí nhỏ nhất

Mã bài: MINCOST

Cho một mạng đối xứng có n đỉnh, mỗi cạnh của mạng có một khả năng thông qua và một cước phí vận chuyển nhất định (như nhau theo cả hai chiều). Cho trước một lượng hàng S cần vận chuyển từ đỉnh nguồn (đánh số là s) tới đỉnh đích (đánh số là f). Hãy tìm một phương án vận chuyển, nghĩa là hãy xác định trên mỗi cạnh của mạng cần vận chuyển bao nhiêu hàng, theo chiều nào, sao cho phù hợp với khả năng thông qua của mạng (trên mỗi cạnh lượng hàng vận chuyển không vượt quá khả năng thông qua của cạnh) và vận chuyển được lượng hàng S từ nguồn về đích với tổng chi phí vận chuyển là nhỏ nhất.
Về mặt toán học, bài toán tìm luồng với chi phí nhỏ nhất có thể diễn đạt như sau:

Cực tiểu hóa hàm chi phí ∑c_ijx_ij với điều kiện:

1. 
   ∑(x_ij - x_ji) với j = 1..n, có giá trị
   
   • 
     S nếu i = s
     
   • 
     0 nếu i ≠ s; i ≠ n
     
   • 
     -S nếu i = f
     
2. 
   0 ≤ x_ij ≤ d_ij với mọi cạnh (i, j)
   

Ở đây đỉnh nguồn được đánh số là s, đỉnh đích là f, c_ij là chi phí vận chuyển một đơn vị hàng trên cạnh (i, j), d_ij là khả năng thông qua của cạnh (i, j); còn x_ij là khối lượng hàng vận chuyển trên cạnh (i, j) cần xác định.

Input

• 
  Dòng đầu là n, m, k, s, f : Số đỉnh, số đường, số đơn vị hàng cần vận chuyển. đỉnh bắt đầu, đỉnh kết thúc
  
• 
  m dòng tiếp theo mỗi bao gồm u, v, c, d cho biết có đường từ u -> v, v -> u với chi phí là c và khả năng thông qua là d.
  

Output

• 
  Dòng đầu, nếu không vận chuyển được ghi –1, nếu có ghi tổng chi phí vận chuyển.
  
• 
  Nếu có nghiệm thì một số dòng tiếp ghi u, v, i cho biết vận chuyển i đơn vị hàng từ trên cạnh u -> v. Kết thúc bằng "0 0 0".
  

Ví dụ:

MINCOST.INP	MINCOST.OUT
6 8 5 1 6 1 2 1 2 1 4 3 4 2 3 1 4 2 5 5 2 3 4 2 4 3 6 1 2 4 6 4 1 5 6 6 2	43 1 2 2 1 4 3 2 5 2 3 6 2 4 3 2 4 6 1 5 6 2 0 0 0

Giới hạn:

• 
  n <= 100
  
• 
  d_ij<= 30000
  
• 
  c_ij<= 10⁹
  

Phạm vi tính toán là Longint.

6. Phòng máy

Mã bài: WIFI

Cuộc thi ACM sắp tới tại thành phố Hồ Chí Minh sẽ có N đội thi. Ban tổ chức bố trí N máy thi cho các đội, đội i ngồi tại vị trí x_i y_i. Để các đội có thể truy cập hệ thống nộp bài dễ dàng, ban tổ chức bố trí M access point. Ban tổ chức muốn tổ chức phòng máy sao cho:

• 
  Mỗi máy tính được kết nối với đúng 1 access point.
  
• 
  Số lượng máy kết nối với các access point chênh lệch không quá 1.
  
• 
  Tổng độ "chập chờn" của mạng là nhỏ nhất. Độ chập chờn của một máy được tính bằng bình phương khoảng cách giữa máy đó với access point mà máy đó kết nối tới.
  

Dữ liệu

• 
  Dòng thứ nhất ghi 2 số M và N.
  
• 
  M dòng tiếp theo, mỗi dòng ghi 2 số là tọa độ của các access point.
  
• 
  N dòng tiếp theo, mỗi dòng ghi 2 số là tọa độ của các máy tính.
  

Kết quả

• 
  Dòng thứ nhất ghi ra tổng độ chập chờn của mạng nhỏ nhất có thể.
  
• 
  Dòng thứ 2 ghi N số. Số thứ i là số hiệu của access point mà máy thứ i kết nối tới.
  

Ví dụ

WIFI.INP	WIFI.OUT
2 3 0 0 2 1 1 0 1 1 1 2	4 1 2 2

Hình vẽ dưới đây mô tả test ví dụ trên. Các máy tính là các hình vuông màu đen, các access point là các hình vuông màu trắng.

Giới hạn

1 ≤ N ≤ 200, 1 ≤ M ≤ 50. Các tọa độ là nguyên và trị tuyệt đối không quá 1000.

7. Trao đổi thông tin

Mã bài: KWAY

Cho một mạng thông tin gồm n trạm và m đường nối hai chiều giữa các trạm. Trạm s là trạm chỉ huy, trạm f là trạm điều khiển. Sau một lần bị tin tặc tấn công lấy mất dữ liệu từ trạm chỉ huy chuyển đến trạm điều khiển, chỉ huy mạng quyết định chia thông tin chuyển đi thành k đơn vị thông tin để chuyển theo k đường đến trạm điều khiển. Mà hai đường truyền bất kỳ không được chung bất kỳ một đường nào.
Hãy tìm cách truyền k đơn vị thông tin sao cho tổng chi phí là nhỏ nhất.

Input

- Dòng đầu là n, m, k, s, f (n ≤ 100).
- m dòng tiếp là u, v, c cho biết có đường từ u -> v và v -> u với chi phí là c.

Output

- Dòng đầu ghi –1 nếu không thể chuyển k đơn vị thông tin theo cách trên, ngược lại ghi chi phi để chuyển.
- k dòng tiếp lần lượt ghi cách chuyển của từng đơn vị thông tin. Số đầu là số lượng trạm trên đường truyền, tiếp đó là dãy các trạm trên đường truyền (bắt đầu từ s, kết thúc ở f)

Chú ý:Phạm vi tính toán là Longint.

Ví dụ:

KWAY.INP	KWAY.OUT
8 11 3 1 8 1 2 1 1 4 1 1 5 1 2 3 1 2 4 1 2 7 1 3 8 1 3 6 1 3 5 1 6 8 1 7 8 1	11 4 1 2 3 8 5 1 5 3 6 8 5 1 4 2 7 8

Каталог: 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: