Ta hotline mạng (network) là một thiết bị thị có hướng G = (V, E), trong số đó bao gồm tuyệt nhất một đỉnh A không tồn tại cung bước vào gọi là vấn đề phân phát (source), tuyệt nhất một đỉnh B không có cung ra đi call là đỉnh thu(sink) và mỗi cung e = (u, v) ∈ E được gán cùng với một số ko âm c(e) = c Gọi là khả năngtrải qua của cung đó (capacity). Để dễ dàng cho bài toán trình bày, ta qui ước rằng nếu như không cócung (u, v) thì kỹ năng trải qua c của nó được gán bằng 0.

You watching:

Quý Khách sẽ xem: Luồng cực lớn c++

Nếu bao gồm mạng G = (V, E). Ta call luồng (flow) f vào mạng G là 1 phxay gán cho từng cung e = (u, v) ∈ E một vài thực ko âm f(e) = f gọi là luồng bên trên cung e, toại ý các điều kiện sau:

Luồng bên trên từng cung không quá thừa tài năng thông qua của nó: 0 ≤ f ≤ c (∀ (u, v) ∈ E).

Với hầu như đỉnh v ko trùng với đỉnh phát A với đỉnh thu B, tổng luồng bên trên các cung lấn sân vào v bằng tổng luồng trên những cung đi thoát ra khỏi v:

*

Trong đó:

Γ-(v) = u∈V⏐(u, v) ∈ E

Γ+(v) = w∈V⏐(v, w) ∈ E

Giá trị của một luồng là tổng luồng bên trên các cung đi thoát ra khỏi đỉnh vạc = tổng luồng trên những cung bước vào đỉnh thu.


*

Mạng cùng với các tài năng trải qua (1 phát, 6 thu) cùng một luồng của chính nó với giá trị 7

10.1. Bài toán

Cho mạng G = (V, E). Hãy kiếm tìm luồng f* trong mạng với mức giá trị luồng lớn nhất. Luồng những điều đó điện thoại tư vấn là luồng cực đại trong mạng và bài xích toán thù này Điện thoại tư vấn là bài bác toán thù kiếm tìm luồng cực đại trên mạng.

10.2. Lát giảm, mặt đường tăng luồng, định lý Ford - Fulkerson

10.2.1. Định nghĩa:

Ta call lát giảm (X, Y) là một giải pháp phân hoạch tập đỉnh V của mạng thành nhì tập rời nhau X cùng Y, trong những số ấy X đựng đỉnh phát với Y chứa đỉnh thu. Khả năng thông qua của lát cắt (X, Y) là tổng tất cả các kỹ năng thông qua của những cung (u, v) gồm u ∈ X và v ∈ Y. Lát giảm với kỹ năng trải qua nhỏtốt nhất hotline là lát giảm hẹp nhất.

10.2.2. Định lý Ford-Fulkerson:

Giá trị luồng cực lớn bên trên mạng đúng bởi kĩ năng trải qua của lát cắt thon duy nhất. Việc minh chứng định lý Ford- Fulkerson vẫn xây dựng được một thuật toán kiếm tìm luồng cực đại bên trên mạng:

Giả sử f là một trong luồng vào mạng G = (V, E). Từ mạng G = (V, E) ta gây ra trang bị thị tất cả trọng số Gf = (V, Ef) như sau:

Xét phần đa cạnh e = (u, v) ∈ E (c > 0):

Nếu f 0 thì ta thêm cung (v, u) vào Ef cùng với trọng số f, cung đó Call là cung nghịch. Về ý nghĩa sâu sắc, trọng số cung này cho thấy thêm còn rất có thể giảm luồng f trên cung (u, v) một lượng không thật trọng số kia.

Đồ thị Gf được gọi là trang bị thị tăng luồng.


*

Mạng G, luồng trên những cung (1 phạt, 6 thu) và vật thị tăng luồng tương ứng

Giả sử P là một lối đi cơ bản tự đỉnh phân phát A cho tới đỉnh thu B. Call ∆ là giá trị bé dại tốt nhất của những trọng số của những cung trê tuyến phố đi P. Ta vẫn đội giá trị của luồng f bằng cách đặt:

• f := f + ∆, nếu (u, v) là cung vào mặt đường Phường và là cung thuận f := f - ∆, giả dụ (u, v) là cung vào mặt đường P.. và là cung nghịch.

Còn luồng bên trên số đông cung khác không thay đổi.

Có thể soát sổ luồng f mới thiết kế vẫn chính là luồng vào mạng và quý giá của luồng f mới được tạo thêm ∆ so với mức giá trị luồng f cũ. Ta Call thao tác biến đổi luồng như vậy là tăng luồng dọc đường Phường, đường đi cơ bạn dạng P trường đoản cú A tới B được Call là con đường tăng luồng.

Ví dụ: với đồ thị tăng luồng Gf nhỏng bên trên, giả sử lựa chọn đường đi (1, 3, 4, 2, 5, 6). Giá trị nhỏ tuổi duy nhất của trọng số trên các cung là 2, vậy thì ta sẽ tăng các giá trị f), f, f, f lên 2, (bởi vì các cung đó là cung thuận) với ưu đãi giảm giá trị f đi 2 (bởi vì cung (4, 2) là cung nghịch). Được luồng new sở hữu quý giá 9.


*

Luồng bên trên mạng G trước với sau khoản thời gian tăng

Đến trên đây ta hoàn toàn có thể hình dung ra được thuật toán thù tra cứu luồng cực to bên trên mạng: khởi chế tạo một luồng bất kỳ, sau đó cứ tăng luồng dọc từ mặt đường tăng luồng, cho đến lúc không tìm được con đường tăng luồng nữa.

Vậy các bước của thuật tân oán search luồng cực lớn bên trên mạng hoàn toàn có thể biểu lộ nlỗi sau:

Bước 1: Khởi tạo:

Một luồng bất kỳ trên mạng, ví dụ như luồng 0 (luồng bên trên những cung đều bằng 0), sau đó:

Cách 2: Lặp hai bước sau:

Tìm con đường tăng luồng P so với luồng hiện nay bao gồm ≡ Tìm lối đi cơ phiên bản tự A tới B bên trên thiết bị thị tăng luồng, trường hợp không tìm kiếm được đường tăng luồng thì bước lặp xong xuôi.

Tăng luồng dọc từ đường P

Cách 3: Thông làm giá trị luồng cực đại tìm kiếm được.

10.3. Cài đặt

Input: file vnạp năng lượng phiên bản MAXFLOW.INPhường. Trong đó:

• Dòng 1: Chứa hẹn số đỉnh n ( ≤ 100), số cạnh m của đồ vật thị, đỉnh phân phát A, đỉnh thu B theo như đúng thiết bị từ bỏ cách nhau tối thiểu một dấu bí quyết.

• m dòng tiếp theo sau, mỗi loại tất cả dạng ba số u, v, c bí quyết nhau ít nhất một vệt cách thểhiện nay có cung (u, v) vào mạng với khả năng trải qua của cung sẽ là c (c là số nguim dương không thực sự 100)

Output: file vnạp năng lượng bạn dạng MAXFLOW.OUT, ghi luồng trên các cung với quý hiếm luồng cực lớn tìm kiếm được.


*

Chụ ý rằng trên từng bước có nhiều giải pháp lựa chọn con đường tăng luồng, hai phương pháp lựa chọn khác nhau có thể mang đến nhì luồng cực đại khác nhau nhưng mà về phương diện cực hiếm thì toàn bộ các luồng thành lập được Theo phong cách bên trên sẽ có cùng giá trị cực đại.

Cài đặt lịch trình tìm kiếm luồng cực đại tiếp sau đây khôn xiết chân phương, trường đoản cú ma trận rất nhiều năng lực trải qua c và luồng f hiện bao gồm (khởi tạo f là luồng 0), nó xây cất đồ dùng thị tăng luồng Gf bằng phương pháp desgin ma trận cf nhỏng sau:

cf = trọng số cung (u, v) bên trên vật dụng thị Gf nếu như như (u, v) là cung thuận.

cf = - trọng số cung (u, v) bên trên vật dụng thị Gf ví như như (u, v) là cung nghịch.

See more: Cách Nấu Cá Ngừ Sốt Cà Chua Của Quân Nguyễn, Làm Sao Nấu Món Cá Ngừ Sốt Cà Chua Đậm Đà

cf = +∞ giả dụ nhỏng (u, v) không hẳn cung của Gf

cf tương tự nhỏng ma trận trọng số của Gf, chỉ tất cả điều ta đổi lốt trọng số nếu như chạm mặt cung nghịch.

Câu hỏi đặt ra là ví như như mạng sẽ cho bao gồm con đường hai phía (bao gồm cả cung (u, v) cùng cung (v, u) - điều này xảy ra không ít trong màng lưới giao thông) thì thứ thị tăng luồng siêu hoàn toàn có thể là nhiều thiết bị thị (thân u, v rất có thể có khá nhiều cung từ bỏ u cho tới v). Ma trận cf cũng gặp gỡ yếu điểm nhỏng ma trận trọng số:

Sau đó lịch trình tra cứu đường đi từ đỉnh phạt A cho tới đỉnh thu B trên đồ vật thị tăng luồng bằng thuậttoán tìm kiếm tìm theo hướng rộng lớn, giả dụ tìm kiếm được đường đi thì đã tăng luồng dọc từ con đường tăng luồng...

P_4_10_1.PAS * Thuật tân oán search luồng cực lớn bên trên mạngprogram Max_Flow;const InputFile = 'MAXFLOW.INP'; OutputFile = 'MAXFLOW.OUT'; max = 100; maxC = 10000;var c, f, cf: array of Integer; c: kỹ năng thông, f: Luồng Trace: array of Integer; n, A, B: Integer; procedure Enter; Nhập mạngvar m, i, u, v: Integer; fi: Text;begin Assign(fi, InputFile); Reset(fi); FillChar(c, SizeOf(c), 0); ReadLn(fi, n, m, A, B); for i := 1 to m vày ReadLn(fi, u, v, c); Close(fi);end;procedure CreateGf; Tìm đồ thị tăng luồng, Có nghĩa là thiết kế cf trường đoản cú c cùng fvar u, v: Integer;begin for u := 1 khổng lồ n vì for v := 1 to n vị cf := maxC; for u := 1 lớn n vày for v := 1 to lớn n vị if c > 0 then Nếu u, v là cung vào mạng begin if f c then cf := c - f; Đặt cung thuận if f > 0 then cf := -f; Đặt cung nghịch end;end;Thủ tục này tra cứu một đường đi từ A cho tới B bằng BFS, trả về TRUE trường hợp bao gồm mặt đường, FALSE ví như không tồn tại đườngfunction FindPath: Boolean;var Queue: array of Integer; Hàng chờ dùng mang đến BFS Free: array of Boolean; u, v, First, Last: Integer;begin FillChar(Free, SizeOf(Free), True); First := 1; Last := 1; Queue := A; Queue chỉ bao gồm một đỉnh phạt A Free := False; lưu lại A repeat u := Queue; Inc(First); Lấy u ngoài Queue for v := 1 khổng lồ n vì if Free and (cf maxC) then Xét v chưa ghi lại kề cùng với u begin Trace := u; Lưu lốt lối đi A → ... → u → v if v = B then v = B thì ta bao gồm lối đi tự A cho tới B, bay thủ tục begin FindPath := True; Exit; end; Free := False; đánh dấu v Inc(Last); Queue := v; Queue ← v end; until First > Last; Queue rỗng FindPath := False; sinh sống bên trên ko Exit được thì tức là không có đườngend;Thủ tục tăng luồng dọc từ con đường tăng luồng kiếm được trong FindPathprocedure IncFlow;var u, v, IncValue: Integer;begin Trước hết dò mặt đường theo vệt để kiếm tìm trọng số nhỏ dại độc nhất của những cung bên trên đường IncValue := maxC; v := B; while v A vì chưng begin u := Trace; Để ý rằng ⏐cf⏐ là trọng số của cung (u, v) bên trên vật dụng thị tăng luồng if Abs(cf) IncValue then IncValue := Abs(cf); v:= u; end; Dò lại con đường lần thứ hai, lần này để tăng luồng v := B; while v A vày begin u := Trace; if cf > 0 then f := f + IncValue Nếu (u, v) là cung thuận bên trên Gf else f := f - IncValue; Nếu (u, v) là cung nghịch bên trên Gf v := u; end;end;procedure PrintResult; In luồng cực lớn tìm đượcvar u, v, m: Integer; fo: Text;begin Assign(fo, OutputFile); Rewrite(fo); m := 0; for u := 1 to lớn n vị for v := 1 to n vì if c > 0 then Nếu bao gồm cung (u, v) trên mạng thì in ra quý hiếm luồng f gán đến cung đó begin WriteLn(fo, 'f(', u, ', ', v, ') = ', f); if u = A then m := m + f; Giá trị luồng cực to = tổng luồng phạt ra từ A end; WriteLn(fo, 'Max Flow: ', m); Close(fo);end;begin Enter; Nhập dữ liệu FillChar(f, SizeOf(f), 0); Khởi tạo ra luồng 0 repeat Cách lặp CreateGf; Dựng vật thị tăng luồng if not FindPath then Break; Nếu không tìm kiếm được con đường tăng luồng thì bay ngay IncFlow; Tăng luồng dọc mặt đường tăng luồng until False; PrintResult;kết thúc.Bây tiếng ta thử coi biện pháp có tác dụng bên trên được sống nơi nào với chưa tốt tại vị trí nào?

Trước hết, thuật toán tra cứu con đường bởi Breadth First Search là hơi xuất sắc, bạn ta sẽ minh chứng rằng giả dụ nhỏng đường tăng luồng được tìm bởi BFS đã có tác dụng sút đáng kể số bước lặp tăng luồng so với DFS.

Nhưng hoàn toàn có thể thấy rằng Việc xây dừng tường minh cả đồ vật thị Gf trải qua bài toán thiết kế ma trận cf chỉ để triển khai từng một việc tìm và đào bới mặt đường là tiêu tốn lãng phí, chỉ cần phụ thuộc vào ma trận kỹ năng trải qua c với luồng f hiện tại có là ta rất có thể biết được (u, v) có phải là cung trên đồ gia dụng thị tăng luồng Gf hay không.

Thứ đọng nhì, trên bước tăng luồng, ta nên dò lại nhị lần đường đi, một lượt nhằm search trọng số bé dại độc nhất vô nhị của các cung trên tuyến đường, một lượt nhằm tăng luồng. Trong khi việc tìm trọng số nhỏ dại tuyệt nhất của những cung trên phố có thể phối kết hợp có tác dụng ngay lập tức vào thủ tục search đường bằng phương pháp sau:

Đặt Delta là trọng số bé dại duy nhất của các cung trên tuyến đường đi trường đoản cú A tới v, khởi tạo ra Delta = +∞.

Tại từng bước một tự đỉnh u thăm đỉnh v trong BFS, thì Delta có thể được tính bởi quý hiếm bé dại duy nhất vào hai giá trị Delta với trọng số cung (u, v) trên đồ vật thị tăng luồng. khi kiếm được lối đi từ bỏ A cho tới B thì Delta đến ta trọng số nhỏ dại nhất của những cung trên phố tăng luồng.

Thđọng cha, tức thì trong bước kiếm tìm đường tăng luồng, ta rất có thể khẳng định ngay lập tức cung như thế nào là cung thuận, cung như thế nào là cung nghịch. Vì vậy Khi từ đỉnh u thăm đỉnh v trong BFS, ta có thể vẫn giữ vết đường đi Trace := u, nhưng mà sau đó đã thay đổi vệt Trace nếu nlỗi (u, v) là cung nghịch.

Những cách tân đó mang đến ta một bí quyết setup hiệu quả hơn, đó là:

10.4. Thuật toánFord- Fulkerson (L.R.FORD & D.R.FULKERSON - 1962)

Mỗi đỉnh v được gán nhãn (Trace, Delta). Trong số đó ⏐Trace⏐ là đỉnh tức tốc trước v trong lối đi từ A cho tới v, Trace âm tốt dương tuỳ theo (⏐Trace⏐, v) là cung nghịch hay cungthuận bên trên vật dụng thị tăng luồng, Delta là trọng số bé dại độc nhất vô nhị của những cung trê tuyến phố đi từ A cho tới v bên trên thiết bị thị tăng luồng.

Bước lặp đã kiếm tìm lối đi trường đoản cú A cho tới B trên thứ thị tăng luồng mặt khác tính luôn luôn các nhãn (Trace, Delta). Sau đó tăng luồng dọc theo mặt đường tăng luồng giả dụ kiếm tìm thấy.

P_4_10_2.PAS * Thuật toán thù Ford-Fulkersonprogram Max_Flow_by_Ford_Fulkerson;const InputFile = 'MAXFLOW.INP'; OutputFile = 'MAXFLOW.OUT'; max = 100; maxC = 10000;var c, f: array of Integer; Trace: array of Integer; Delta: array of Integer; n, A, B: Integer;procedure Enter; Nhập dữ liệuvar m, i, u, v: Integer; fi: Text;begin Assign(fi, InputFile); Reset(fi); FillChar(c, SizeOf(c), 0); ReadLn(fi, n, m, A, B); for i := 1 to lớn m do ReadLn(fi, u, v, c); Close(fi);end;function Min(X, Y: Integer): Integer;begin if X Y then Min := X else Min := Y;end;function FindPath: Boolean;var u, v: Integer; Queue: array of Integer; First, Last: Integer;begin FillChar(Trace, SizeOf(Trace), 0); Trace = 0 đồng nghĩa cùng với v không tiến công dấu First := 1; Last := 1; Queue := A; Trace := n + 1; Chỉ yêu cầu nó không giống 0 nhằm đánh dấu mà thôi, số dương làm sao cũng khá được cả Delta := maxC; Khởi sản xuất nhãn repeat u := Queue; Inc(First); Lấy u khỏi Queue for v := 1 khổng lồ n bởi if Trace = 0 then Xét nhứng đỉnh v không đánh dấu thăm begin if f c then Nếu (u, v) là cung thuận bên trên Gf với bao gồm trọng số là c - f begin Trace := u; Lưu vết, Trace mang vệt dương Delta := min(Delta, c - f); kết thúc else if f > 0 then Nếu (u, v) là cung nghịch bên trên Gf cùng tất cả trọng số là f begin Trace := -u; Lưu lốt, Trace mang vệt âm Delta := min(Delta, f); end; if Trace 0 then Trace không giống 0 có nghĩa là từ bỏ u hoàn toàn có thể thăm v begin if v = B then Có con đường tăng luồng từ bỏ A tới B begin FindPath := True; Exit; end; Inc(Last); Queue := v; Đưa v vào Queue end; end; until First > Last; Hàng hóng Queue rỗng FindPath := False; sinh sống trên không Exit được Tức là không tồn tại đườngend;procedure IncFlow; Tăng luồng dọc con đường tăng luồngvar IncValue, u, v: Integer;begin IncValue := Delta; Nhãn Delta chính là trọng số nhỏ dại tuyệt nhất trên những cung của đường tăng luồng v := B; Truy lốt đường đi, tăng luồng dọc từ đường đi repeat u := Trace; Xét cung (⏐u⏐, v) trê tuyến phố tăng luồng if u > 0 then f := f + IncValue , v) là cung thuận thì tăng f else begin u := -u; f := f - IncValue; u end; v := u; until v = A;end;procedure PrintResult; In kết quảvar u, v, m: Integer; fo: Text;begin Assign(fo, OutputFile); Rewrite(fo); m := 0; for u := 1 to lớn n bởi vì for v := 1 khổng lồ n vị if c > 0 then begin WriteLn(fo, 'f(', u, ', ', v, ') = ', f); if u = A then m := m + f; end; WriteLn(fo, 'Max Flow: ', m); Close(fo);end;begin Enter; FillChar(f, SizeOf(f), 0); repeat if not FindPath then Break; IncFlow; until False; PrintResult;kết thúc.Định lý về luồng cực lớn trong mạng với lát cắt khiêm tốn nhất:

Luồng cực lớn vào mạng bằng khả năng trải qua của lát giảm dong dỏng tốt nhất. Lúc vẫn kiếm được luồng cực lớn thì theo thuật tân oán trên sẽ không tồn tại đường đi tự A cho tới B trên vật thị tăng luồng. Nếu đặt tập Xtất cả hầu hết đỉnh cho được từ đỉnh phân phát A trên đồ thị tăng luồng (tất yếu A∈X) cùng tập Y gồmnhững đỉnh còn sót lại (tất yếu B∈Y) thì (X, Y) là lát cắt nhỏ bé duy nhất kia. cũng có thể có không ít lát giảm bé tốt nhất,ví dụ nếu đặt tập Y tất cả hồ hết đỉnh mang lại được đỉnh thu B bên trên trang bị thị tăng luồng (tất nhiên B∈ Y) vàtập X bao gồm số đông đỉnh còn sót lại thì (X, Y) cũng là 1 trong những lát giảm không lớn tốt nhất.

Định lý về tính nguyên:

Nếu tất cả những kỹ năng trải qua là số ngulặng thì thuật toán thù bên trên luôn tìm được luồng cực to cùng với luồng trên cung là các số ngulặng. Vấn đề này rất có thể minh chứng rất giản đơn vị thuở đầu khởi tạo ra luồng 0thì tức các luồng trên cung là nguyên. Mỗi lần tăng luồng lên một lượng bởi trọng số nhỏ dại độc nhất trênnhững cung của đường tăng luồng cũng là số nguyên ổn buộc phải sau cùng luồng cực lớn tất đã nên tất cả luồngtrên các cung là nguyên.

Định lý về ngân sách thời gian triển khai giải thuật:

Trong phương pháp Ford-Fulkerson, giả dụ dùng lối đi nthêm độc nhất vô nhị (qua ít cạnh nhất) trường đoản cú đỉnh phân phát tới đỉnh thu bên trên trang bị thị tăng luồng thì cần ít hơn n.m lần chọn đường đi để tìm thấy luồng cực to.

Edmonds với Karp đã minh chứng tính chất này với ý kiến đề xuất một phương thức cải tiến: Tại mỗi bước, ta nên kiếm tìm con đường tăng luồng sao để cho cực hiếm tăng luồng được tăng thêm các tốt nhất.

Nói thông thường so với thuật toán thù Ford-Fulkerson, những đánh giá kim chỉ nan bị lệch rất nhiều đối với thực tế, mặc dù với sự đối chiếu vào ngôi trường phù hợp xấu, chi phí thời hạn thực hiện của thuật toán thù là tương đối lớn.

Nhưng bên trên thực tiễn thì thuật toán thù này hoạt động vô cùng nkhô hanh cùng tác dụng.

Bài tập:

Bài 1

Mạng với tương đối nhiều điểm vạc và nhiều điểm thu: Cho một mạng gồm n đỉnh cùng với p điểm phát A1, A2, ..., Ap cùng q điểm thu B1, B2, ..., Bq. Mỗi cung của mạng được gán kĩ năng thông qua là số ngulặng. Các đỉnh phát chỉ gồm cung rời khỏi cùng những đỉnh thu chỉ bao gồm cung lấn sân vào. Một luồng bên trên mạngnày là một trong những phxay gán cho từng cung một vài thực Gọi là luồng trên cung đó không vượt thừa khả năngthông qua cùng hợp ý cùng với mỗi đỉnh không hẳn đỉnh vạc giỏi đỉnh thu thì tổng luồng đi vào bằngtổng luồng đi ra. Giá trị luồng bởi tổng luồng đi ra trường đoản cú những đỉnh vạc = tổng luồng đi vào các đỉnhthu. Hãy tra cứu luồng cực đại bên trên mạng.

Bài 2

Mạng với kĩ năng thông qua của những đỉnh với các cung: Cho một mạng với đỉnh phân phát A và đỉnh thu B. Mỗi cung (u, v) được gán kĩ năng trải qua c. Mỗi đỉnh v khác cùng với A cùng B được gánCác thuật toán bên trên vật thịtài năng thông qua d. Một luồng trên mạng được có mang như lúc trước cùng thêm điều kiện: tổngluồng lấn sân vào đỉnh v không được thừa vượt tài năng trải qua d của đỉnh kia. Hãy tìm kiếm luồng cực to trên mạng.

See more: 4+ Cách Làm Bùa Yêu Tại Nhà Hiệu Quả Nhất, Cách Làm Bùa Yêu Bằng Tên Tuổi Hiệu Quả Tốt Nhất

Bài 3

Lát cắt nhỏ nhắn nhất: Cho một vật dụng thị bao gồm n đỉnh cùng m cạnh cùng 2 đỉnh A, B. Hãy tra cứu biện pháp bỏ đi một số ít nhất những cạnh để không hề lối đi tự A tới B.

Bài 4

Một lớp học bao gồm n bạn nam, n bạn nữ. Cho m món đá quý lưu giữ niệm, (n ≤ m). Mỗi bạn gồm sở thích về một số trong những món kim cương nào đó. Hãy tìm kiếm giải pháp phân cho từng các bạn nam Tặng Ngay một món vàng cho 1 bạn gái thoả mãn:

Mỗi các bạn nam giới chỉ bộ quà tặng kèm theo quà mang đến đúng một chúng ta nữ

Mỗi bạn nữ chỉ nhận kim cương của đúng một chúng ta nam