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ị



tải về 418.79 Kb.
trang5/8
Chuyển đổi dữ liệu21.08.2016
Kích418.79 Kb.
#25787
1   2   3   4   5   6   7   8

Chuyên đề: CẶP GHÉP

  1. Cặp ghép không trọng số

Mã bài: MATCH1


Cho đồ thị hai phía G = (X U Y, E); Các đỉnh của X ký hiệu là x1, x2, ..., xm, các đỉnh của Y ký hiệu là y1, y2, ..., yn.
Một bộ ghép trên G là một tập các cạnh thuộc E đôi một không có đỉnh chung.

Yêu cầu: Hãy tìm bộ ghép cực đại (có nhiều cạnh nhất) trên G.

Chú ý : Dùng Eof chứ không dùng SeekEof.

Input


• Dòng 1: Chứa hai số m, n (1 ≤ m, n ≤ 100)
• Các dòng tiếp, mỗi dòng chứa hai số nguyên dương i, j cho biết thông tin về một cạnh (xi, yj) thuộc E.

Output


• Dòng 1: Ghi số cạnh trong bộ ghép cực đại tìm được (K).
• K dòng tiếp theo, mỗi dòng ghi thông tin về một cạnh được chọn vào bộ ghép cực đại: Gồm 2 số u, v thể hiện cho cạnh nối (xu, yv).

Example



MATCH1.INP

MATCH1.OUT

4 5

1 1


1 4

2 1


2 2

2 4


3 2

3 3


4 2

4 3


4

1 1


2 4

3 3


4 2


  1. Bộ ghép đầy đủ trọng số cực tiểu

Mã bài: MATCH2


Cho đồ thị hai phía G = (X U Y, E); Các đỉnh của X ký hiệu là x1, x2, ..., xn, các đỉnh của Y ký hiệu là y1, y2, ..., yn. Mỗi cạnh của G được gán một trọng số không âm. Một bộ ghép đầy đủ trên G là một tập n cạnh thuộc E đôi một không có đỉnh chung. Trọng số của bộ ghép là tổng trọng số các cạnh nằm trong bộ ghép.

Ràng buộc: Luôn tồn tại ít nhất một bộ ghép đầy đủ trên G.
Chú ý dùng Eof chứ không dùng SeekEof

Input


• Dòng 1: Chứa số n (1 ≤ n ≤ 200)
• Các dòng tiếp theo, mỗi dòng chứa 3 số nguyên i, j, c cho biết có một cạnh (xi, yj) và trọng số cạnh đó là c (0 ≤ c ≤ 200).

Output


• Dòng 1: Ghi trọng số bộ ghép tìm được
• n dòng tiếp, mỗi dòng ghi hai số (u, v) tượng trưng cho một cạnh (xu, yv) được chọn vào bộ ghép.

Example

MATCH2.INP

MATCH2.OUT

4

1 1 0


1 2 0

2 1 0


2 4 2

3 2 1


3 3 0

4 3 0


4 4 9

3

1 1


2 4

3 2


4 3

  1. Cặp ghép cực đại trên đồ thị hai phía

Mã bài: NKBM


Trong lý thuyết đồ thị, một cặp ghép hay tập cạnh độc lập của một đồ thị là một tập các cạnh không có đỉnh chung. Bài toán ghép cặp thường được quan tâm trong trường hợp đồ thị hai phía. Đồ thị đơn vô hướng G=(V,E) là một đồ thị hai phía nếu như tồn tại một cách phân hoạch tập đinh V thành hai tập V1, V2 sao cho mỗi cạnh thuộc E đều có dạng v1v2 với v1 thuộc V1, v2 thuộc V2. Một ví dụ đó là bài toán sắp xếp công việc. Giả sử có P người và J công việc, mỗi người có thể làm một số công việc nào đó. Ta mô hình bài toán bằng một đồ thị hai phía với P+J đỉnh. Nếu người pi có thể làm công việc ji thì có một cạnh giữa hai đỉnh pi và ji trên đồ thị.

Tìm một cặp ghép cực đại (còn được gọi là cặp ghép có lực lượng lớn nhất) trên một đồ thị hai phía G=(V=(X,Y), E) là một bài toán quen thuộc và đơn giản trong lý thuyết đồ thị. Định lý Konig chỉ ra rằng trong một đồ thị hai phía, kích thước của cặp ghép cực đại bằng kích thước của phủ đỉnh nhỏ nhất. Từ kết quả này, bài toán phủ đỉnh nhỏ nhất và bài toán tập độc lập lớn nhất trên đồ thị hai phía có thể giải được trong thời gian đa thức.

Bạn hãy thử giải quyết bài toán tìm cặp ghép cực đại trên đồ thị hai phía: cho biết đồ thị hai phía G=(V=(X,Y), E), hãy tìm cặp ghép cực đại (có nhiều cạnh nhất).

Dữ liệu


  • Dòng đầu tiên chứa hai số x, y, m (x, y ≤ 1000), theo thứ tự là số đỉnh thuộc tập X, tập Y của đồ thị và số cạnh nối.

  • m dòng tiếp theo mỗi dòng ghi hai số i, j cách nhau bởi một dấu cách thể hiện có cạnh nối giữa hai đỉnh xi, yj.

Kết qủa


In ra kích thước của cặp ghép cực đại.

Ví dụ

NKBM.INP

NKBM.OUT

4 5 9

1 1


1 4

2 1


2 2

2 4


3 2

3 3


4 2

4 3


4

  1. Phân công hoàn thành sớm nhất

Mã bài: ASSIGN1


Có n người, n việc (1 < n ≤ 200). Người thứ i thực hiện công viêc j mất C[i,j] đơn vị thời gian. Giả sử tất cả bắt đầu vào thời điểm 0, hãy tìm cách bố trí mỗi công việc cho mỗi người sao cho thời điểm hoàn thành công việc là sớm nhất có thể.

Input


- Dòng đầu: N
- Tiếp theo là ma trận C[i,j]. (thuộc kiểu Integer)

Output


- Ghi thời điểm sớm nhất hoàn thành.

Example

ASSIGN1.INP

ASSIGN1.OUT

4

10 10 10 2

10 10 3 10

4 10 10 10

10 5 10 10


5

  1. Boxes

Mã bài: BOXES


Có n cái hộp xếp theo vòng tròn đánh số 1..n (1 ≤ n ≤ 1000) theo chiều kim đồng hồ. Mỗi hộp chứa một số quả bóng, tổng số quả bóng không quá n.

Cần dịch chuyển các quả bóng sao cho mỗi hộp không chứa quá 1 quả. Mỗi bước, ta có thể di chuyển một quả bóng từ một hộp sang một trong hai hộp bên cạnh.

Tính số bước di chuyển ít nhất.

Dữ liệu


Dòng đầu tiên chứa t là số bộ test (t ≤ 20). Mỗi bộ test có dạng:

  • Dòng đầu tiên: n - số hộp.

  • Dòng thứ hai: n số nguyên không âm là số quả bóng trong các hộp

Kết quả


Với mỗi bộ test in ra số bước ít nhất cần thiết.

Ví dụ

BOXES.INP

BOXES.OUT

1

12

0 0 2 4 3 1 0 0 0 0 0 1
19

  1. IOI2008

Mã bài: IOI2008


IOI 2008 diễn ra trong n + 1 ngày, các bài toán của IOI được đánh số từ 1 tới n.(n+1) và được phân bố vào các ngày thi theo lịch sau (mỗi ngày thi có n bài toán):

Ngày 1: Các bài toán từ 1 tới n

Ngày 2: Các bài toán từ n + 1 tới 2n

...


Ngày i: Các bài toán từ (i - 1).n + 1 tới i.n

...


Ngày n+1: Các bài toán từ n.n + 1 tới n.(n+1)

Các bài thi có một trong k dạng, bài thứ j có dạng là rj (1 <= rj<= k)

Thể thức thi được thông báo cho mỗi đoàn như sau:

- Mỗi đoàn sẽ có n + 1 học sinh tham gia

- Hàng ngày, Ban tổ chức sẽ đưa một học sinh của đoàn đi tham quan thành phố, việc chọn học sinh nào cho đi tham quan là quyền của trưởng đoàn, nhưng phải đảm bảo điều kiện:

Cho đến khi IOI kết thúc, học sinh nào của đoàn cũng đã được đi tham quan thành phố. Như vậy mỗi ngày đoàn sẽ còn lại n học sinh tham gia thi, việc giao cho học sinh nào làm bài nào là quyền của phó đoàn nhưng mỗi học sinh chỉ được giao một bài và hai học sinh khác nhau sẽ phải nhận hai bài khác nhau.

Kết thúc IOI, điểm đồng đội của mỗi đoàn sẽ được tính bằng tổng điểm của tất cả các lời giải các bài toán đã cho.

Các thầy giáo trưởng, phó đoàn Việt Nam dự đoán rằng nếu học sinh thứ i của đoàn làm bài toán dạng j thì có thể thu được số điểm là cij (cij = 0 tương đương với lời dự đoán rằng học sinh thứ i không làm được bài toán dạng j).

Hỏi các thầy sẽ sắp xếp lịch thi đấu cho các học sinh như thế nào để theo dự đoán, đoàn Việt Nam sẽ thu được số điểm nhiều nhất có thể.

Input


Dòng 1: Chứa hai số n, k (1 <= n <= 100; 1 <= k <= 1000)

Dòng 2: Chứa n.(n+1) số, số thứ p là rp.

Các dòng tiếp, mỗi dòng chứa ba số nguyên dương i, j, p cho biết một điều dự đoán của các thầy: học sinh thứ i có thể làm được bài toán dạng j và đạt được số điểm là p (=c[i, j]). (1 <= p <= 100)

Output


Gồm 1 dòng duy nhất : Ghi điểm đồng đội mà theo dự đoán đoàn Việt Nam có thể đạt

Ví dụ:

IOI2008.INP

IOI2008.OUT

3 4

1 2 4 4 3 3 1 4 2 3 2 2

1 1 2

1 2 3


1 4 6

2 3 4


2 1 3

2 4 7


3 2 1

3 1 4


4 1 2

4 3 9


4 2 8

65

  1. Harry Potter và mê cung tử thần

Mã bài: NHP


Trong chuyến phiêu lưu tìm kiếm những bảo bối tử thần, Harry cùng các bạn của cậu đã lạc vào một mê cung bí mật. Ngay khi họ vừa bước chân vào, các bức tường lập tức mọc lên bốn phía, chia mê cung thành N*N phòng có kích thước 1*1 và nhóm của Harry bị nhốt trong một số phòng. Mỗi phòng đều có 4 cánh cửa, mỗi chiếc nằm trên 1 bức tường của phòng đó.

Các con quái vật chỉ xuất hiện trong các phòng có Harry và các bạn của cậu. Số quái vật ở một phòng luôn luôn bằng số người trong phòng. Điều này có nghĩa là khi 1 người di chuyển từ phòng X sang phòng Y, thì ở phòng Y sẽ có thêm 1 con quái vật.

Để sống sót, buộc Harry và các bạn phải chiến đấu với lũ quái vật và tìm đường thoát ra ngoài. Thời gian để tiêu diệt 1 con quái vật ở phòng (I, J) là A[I, J]. (Đánh số các phòng từ trái sang phải, từ trên xuống dưới). Một người chỉ có thể cùng 1 lúc chiến đấu với 1 con quái vật, và bắt buộc phải tiêu diệt xong quái vật đó mới có thể chuyển sang phòng khác.

Nhờ tấm bản đồ đạo tặc, Harry biết được những người bạn của mình đang ở phòng nào. Cậu cũng phát hiện ra rằng, mỗi phòng nhốt bạn mình đều được sơn bằng một màu riêng biệt, và các cánh cửa nằm trên 4 bức tường bao ngoài của mê cung cũng có nhiều màu sắc khác nhau. Bây giờ cậu cần phải hướng dẫn từng người chạy tới cánh cửa cùng màu với phòng nhốt người đó. Nhưng khi có một người thoát ra ngoài mê cung, thì ngay lập tức, quái vật trong mê cung sẽ hồi phục lại sức mạnh như ban đầu, và 4 bức tường của căn phòng bí mật sẽ quay 1 đơn vị theo chiều kim đồng hồ, làm các cánh cửa màu trên đó cũng quay theo. Hay nói cách khác, nếu ta đi dọc theo 4 bức tường của căn phòng bí mật theo chiều kim đồng hồ thì mỗi cánh cửa mà ta đi tới sẽ đổi sang màu cũ của cánh cửa ngay phía sau ta (Xem hình vẽ).


Do tình thế khó khăn nên chỉ khi một người thoát khỏi mê cung thì Harry mới hướng dẫn người tiếp theo. Bạn hãy giúp Harry hướng dẫn cho tất cả các bạn của mình thoát khỏi mê cung trong thời gian ngắn nhất!

(P/s: Nếu bạn hỏi Harry hướng dẫn cho các bạn mình bằng cách nào? Cậu ấy dùng thần chú “Sonorus!” (Âm vang) làm giọng nói của mình vang vọng khắp mê cung. :D)


Dữ liệu


Dòng đầu ghi 2 số nguyên dương N, K. Với N là kích thước của mê cung, K là số người trong nhóm bạn của Harry.

Trong I dòng tiếp theo, mỗi dòng ghi J số nguyên không âm. Số thứ J trên dòng I là A[I, J] thể hiện thời gian cần thiết để tiêu diệt quái vật trong phòng (I, J).

Trong K dòng tiếp, mỗi dòng ghi 1 bộ 3 số nguyên không âm I, J, C. Bộ số (I, J, C) trên dòng thứ X thể hiện rằng người bạn thứ X đang ở phòng (I, J) và phòng này được sơn màu C.

Dòng cuối cùng ghi 4*N số nguyên không âm, là màu của các cánh cửa trên 4 bức tường bao quanh mê cung, lần lượt theo chiều kim đồng hồ, bắt đầu từ cánh cửa ở bức tường phía trên của phòng nhỏ (1,1). (Thứ tự giống như trong hình 1)


Kết quả


Một số nguyên duy nhất là thời gian nhỏ nhất để tất cả mọi người trong nhóm bạn của Harry có thể thoát khỏi mê cung.

Giới hạn


  • 1 ≤ N ≤ 100

  • 1 ≤ K ≤ 100, K ≤ N^2

  • 0 ≤ C ≤ 100

  • 0 ≤ A[I, J] ≤ 100

Ví dụ

NHP.INP

NHP.OUT

3 2

2 2 2


0 2 0

1 0 2


1 2 2

2 1 2


2 2 2 2 2 2 1 1 2 1 1 2

3

  1. Fast Maximum Matching

Mã bài: FMATCH


FJ có N (1 ≤ N ≤ 50,000) cô bò và M (1 ≤ M ≤ 50,000) chú bò. Cho danh sách P (1 ≤ P ≤ 150,000) khả năng ghép đôi giữa các cô bò và chú bò, hãy tính số cặp lớn nhất có thể ghép được. Tất nhiên, một cô bò có thể ghép với tối đa là một chú bò và ngược lại.

Dữ liệu vào:


Dòng đầu tiên chứa 3 số nguyên, N, M, và P. Mỗi dòng trong số P dòng tiếp theo chứa 2 số nguyên A (1 ≤ A ≤ N) và B (1 ≤ B ≤ M), thể hiện việc cô bò A có thể ghép được với chú bò B.

Kết quả ra:


In ra một số nguyên thể hiện số cặp lớn nhất có thể đạt được.

Ví dụ:

FMATCH.INP

FMATCH.OUT

5 4 6

5 2


1 2

4 3


3 1

2 2


4 4

3

Cô bò 1 có thể được ghép với chú bò 2, cô bò 3 với chú bò 1, và cô bò 4 với chú bò 3.



tải về 418.79 Kb.

Chia sẻ với bạn bè của bạn:
1   2   3   4   5   6   7   8



Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2024
được sử dụng cho việc quản lý
    Quê hương
BÁO CÁO
Tài liệu