QUI HOẠCH ĐỘNG TRÊN ĐỒỒ THỊ CÓ HƯỚNG, KHỒNG CHU TRÌNH
Giải các bài toán có nội dung đồồ thị là một phầồn quan trọng trong chương trình tin
học khuồn khổ chuyên đêồ này, tồi chỉ xin trao đổi với các bạn đồồng nghiệp m ột nội dung
nhỏ của lý thuyêết đồồ thị là "Các bài toán qui hoạch động trên đồồ thị có hướng, khồng có
chu trình".
Chuyên đêồ trình bày một sồế kinh nghiệm khi dạy vêồ đồồ th ị có h ướng khồng chu trình.
Một trong những điêồu khá lý thú là ở đầy hai nội dung chính của chương trình tin h ọc là
Qui hoạch động và lý thuyêết đồồ thị được kêết hợp. Chính điêồu này cho phép xầy d ựng cho
học sinh một cách nhìn tổng quan khi tiêếp cận cả hai dạng toán này.
Phầồn lớn các ví dụ minh họa trong chuyên đêồ được lầếy từ các kỳ thi học sinh giỏi
khác nhau. Mục đích làm như vậy là tồi muồến trao đổi với các bạn đồồng nghiệp vêồ cách
xầy dựng một đêồ toán đồồ thị sao cho vừa có thể ồn tập kiêến thức học sinh, v ừa có th ể bám
sát được chương trình thi trong các kỳ thi học sinh giỏi tin học.
I-MỘT SỒỐ KHÁI NIÊM VÀ BÀI TOÁN CƠ BẢN
Như chúng ta đã biêết, đồồ thị có thể được hình dung như là một cặp (V, E) trong đó V
là tập hợp các đỉnh (trong các bài toán tin học thì V là tập hợp hữu hạn các đỉnh có thể
đánh sồế 1, 2, ..., N) còn E là tập hợp các cung của đồồ thị.
Một đồồ thị có hướng khồng có chu trình là đồồ th ị khồng tồồn tại đường đi khép kín.
Cũng có thể hình dung đầy là đồồ thị mà sồế lượng đỉnh trong tầết cả các thành phầồn liên
thồng mạnh đêồu bằồng 1.
Một đồồ thị có hướng khồng có chu trình luồn tồồn tại một sắắp xếắp topo. Chính xác
hơn, một sằếp xêếp topo là một cách sằếp xêếp các đỉnh của đồồ thị thành một dãy
x1 , x2 ,L , xn
Sao cho mọi cung
( xi , x j ) E
đêồu kéo theo i < j.
Việc chỉ ra một sằếp xêếp topo trên đồồ thị có hướng khồng có chu trình là điêồu kiện
tiên quyêết để làm các bài toán qui hoạch động trên loại đồồ thị này. Lý do đ ơn giản là nêếu
như coi mồỗi đỉnh của đồồ thị là một trạng thái thì với việc sằếp xêếp topo chúng ta có một
thứ tự trên các trạng thái này và đầy chính là cách tiêếp cận vầến đêồ theo quan điểm qui
hoạch động.
Có hai cách chính đêồ xầy dựng một sằếp xêếp topo trên đồồ thị có hướng khồng có chu
trình:
Cách thứ nhấắt: Dựa vào một tiêu chí tự nhiên mà nêếu sằếp xêếp tằng/giảm theo tiêu chính
này thì đương nhiên ta có một sằếp xêếp topo.
r , r ..., r
Ví dụ 1 (VOI 2008): Cho n hình tròn bán kính 1 2, n . Ta nói từ đường tròn bán kính a có
thể nhảy tới hình tròn bán kính b nêếu tồồn tại một hình tròn bán kính c sao cho a+c=b (*) .
Hãy tìm đường đi qua nhiêồu hình tròn nhầết.
Dêỗ nhận thầếy rằồng điêồu kiện (*) chứng tỏ từ một hình tròn chỉ có thể nhảy đêến một
hình tròn có bán kính lớn hơn nên hiển nhiên rằồng nêếu ta sằếp xêếp lại các hình tròn sao cho
bán kính của chúng tằng dầồn ta seỗ có một sằếp xêếp topo.
Thồng thường các tiêu chí tự nhiên này thường dêỗ thầếy và việc sằếp xêếp topo qui vêồ
việc sằếp xêếp tằng/giảm trên tiêu chí này. Do đó, hiển nhiên tiêu chí sằếp xêếp ph ải d ựa trên
dữ liệu có mồếi quan hệ sằếp xêếp hoàn toàn (thồng thường là các sồế).
Cách thứ hai: Dựa vào thuật toán Tarjan tìm thành phầồn liên thồng mạnh. Chú ý rằồng khi
đồồ thị là khồng có chu trình thì các thành phầồn liên thồng m ạnh đêồu có sồế l ượng đ ỉnh bằồng
1. Do vậy trong trường hợp này ta chỉ cầồn liệt kê các đỉnh theo thứ tự sau của phép duyệt
đồồ thị ưu tiên chiêồu sầu. Mã giả của nó được viêết như dưới đầy
PROCEDURE visit(u)
Đánh dấu u được thăm
For v Ke(u) do if (v chưa được thăm) then
visit(v)
Đưa u vào danh sách sắp topo
(Có thể tham khảo mã Pascal trong sách giáo khoa chuyên tin. Tập 1)
Cách thứ hai được dùng khi khồng thể tìm được tiêu chí tự nhiên trong việc sằếp xêếp
topo. Tuy rằồng đầy là cách tổng quát áp dụng cho mọi trường hợp nhưng theo kinh
nghiệm của tồi thì thồng thường khi sằếp xêếp topo ta hay sử dụng cách th ứ nhầết h ơn.
Giả sử trên đồồ thị có hướng khồng có chu trình G=(V,E) ta đã có một sằếp xêếp topo
x1 , x2 ,..., xn . Khi đó ta có hai bài toán cơ bản sau:
Bài toán 1: Cho mồỗi cung của đồồ thị một trọng sồế. Hãy tìm đường đi dài nhầết từ đỉnh s
đêến đỉnh t
Đặt f [ xi ] lầồn là độ dài đường đi dài nhầết từ s đêến xi. Khi đó
f [ xi ] max{f [ xk ] d ( xk , xi ) : ( xk , xi ) E}
Một điêồu lý thú là thay vì tính toán trên các cung ngược (các cung tới xi ) của đồồ thị
theo như cách tư duy truyêồn thồếng của qui hoạch động, chúng ta seỗ s ửa (update) theo các
cung xuồi (đầy là đặc điểm chính khi thực hiện qui hoạch động trên DAG vì nói chung xầy
dựng các cung ngược là một vầến đêồ khá phức tạp):
PROCEDURE DuongDiMax
For i {1,...,n} f[i]=-
For i {1,...,n}
u=x[i]
if (u=s) f[u]=0
if (f[u]<>-)
For v Ke(u) if f[v]
-)
For v Ke(u) f[v]=f[v]+f[u]
Hai bài toán trên là hai bài toán cơ bản trong các bài toán qui hoạch động trên đồồ
thị có hướng. Một lầồn nữa nhằếc lại điêồu đặc biệt của qui hoạch động trên đồồ thị có hướng
là ta tính toán theo cung của đồồ th ị, do vậy ta thực hi ện việc sửa (update) nhãn thay vì
tính max, tính min hoặc đêếm như trong qui hoạch động thồng th ường (lý do đ ơn gi ản là
xầy dựng đồồ thị ngược nói chung là khá phức tạp và tồến kém)
II-MỘT SỒỐ BÀI TẬP MINH HỌA
Bài tập 1 (VOI 2008):
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 veỗ 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 veỗ 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 veỗ mũi tên là: Nêếu có ba sồế ai, aj,
ak thỏa mãn ak = ai + aj thì veỗ 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 đã veỗ để đi đêến các vòng tròn khác. Người thằếng cuộc seỗ là ng ười tìm
được cách di chuyển qua nhiêồu vòng tròn nhầết.
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.
Như phầồn trước đã nhận xét, nêếu coi mồỗi vòng tròn là một đỉnh của đồồ th ị. Hai vòng
tròn kêồ nhau nêếu có thể nhảy trực tiêếp đêến nhau thì ta có một DAG và bài toán qui vêồ tìm
đường đi dài nhầết trên đồồ thị này.
Một điểm cầồn lưu ý là để chương trình chạy đạt yêu cầồu thì điêồu kiện j Ke(i) cầồn
thực hiện việc tìm kiêếm nhị phần để kiểm tra
Bài tập 2:
Một ông chủ có 2 cái máy cày cho thuê, có N người nông dân đăng ký thuê máy cày. Người
thứ i muốn thuê máy bắt đầu từ thời điểm s[i] đến hết thời điểm t[i]. Giá thuê một máy cày
trong một đơn vị thời gian mất một đồng, như vậy nếu cho người thứ i thuê ông chủ có thể thu
về được t[i]-s[i]+1 đồng. Tại một thời điểm một máy có nhiều nhất một người sử dụng.
Yêu cầu: Tính số tiền nhiều nhất có thể thu được.
Input:
- Dòng đầu là số nguyên N (N<=100)
- N dòng sau, mỗi dòng 2 số nguyên thể hiện số s[i], t[i] (0<=s[i]<=t[i]<=109)
Output:
- Gồm 1 dòng duy nhất chứa 1 số là số tiền lớn nhất có thể thu được.
Ta xầy dựng đồồ thị như sau:
Tập đỉnh V={(i,j): với ý nghĩa là máy thứ nhầết làm cồng việc cuồếi cùng là i và máy
thứ hai làm cồng việc cuồếi cùng là j}
Tập cung E={(i,j)-(i,k): nêếu sau khi làm j máy thứ 2 làm được cồng việc k và (i,j)-(k,j)
nêếu sau khi làm i máy thứ nhầết làm được k}
Dêỗ thầếy bài toán qui vêồ tìm đường đi dài nhầết từ đỉnh (0,0).
Đầy là DAG và một sằếp xêếp topo tự nhiên là sằếp xêếp theo th ời gian kêết thúc thuê máy
tằng dầồn. Do vậy ta hoàn toàn có thể sử dụng mồ hình bài toán 1 để gi ải quyêết:
Bài tập 3:
Cho đồồ thị có hướng N đỉnh (N≤16) trong đó các cạnh có trọng sồế. Hãy tìm đ ường đi
Haminton (đường đi qua tầết cả các đỉnh) ngằến nhầết?
Ta xầy dựng một đồồ thị mới trong đó mồỗi đỉnh là một cặp gồồm dãy bit ( b1 , b2 ,..., bn )
với bi 1 nêếu như đỉnh i đã đi qua còn bi 0 nêếu như đỉnh i chưa đi qua và đỉnh u thể
hiện đỉnh cuồếi cùng trên hành trình là u . Như vậy mồỗi đỉnh là một cặp (x, u) với x là sồế
nguyên thể hiện dãy bit trên. Đỉnh (x, u) đi đêến được (y,v) nêếu như bit v của x bằồng 0 và
bít v của y bằồng 1 (các bit khác trùng nhau) và u đi đêến được v.
Dêỗ thầếy rằồng đồồ thị xầy dựng như trên là DAG với sằếp xêếp topo tự nhiên là sằếp xêếp
các đỉnh (x, u) theo sồế lượng bit 1 của x tằng dầồn. Khi đó trên sằếp xêếp topo này các đỉnh
được chia thành từng lớp (x có 0 bit 1, x có 1 bit 1, ...., x có n bit 1) và ta có thể s ử d ụng mồ
hình bài toán 1 (tìm đường đi dài nhầết từ tập đinh có 1 bit 1 đêến tập đ ỉnh có n bít 1) v ới
một chút cải tiêến là kêết hợp với một hàng đợi.
III-CÁC ĐỒỒ THỊ CÓ HƯỚNG KHỒNG CÓ CHU TRÌNH CẢM SINH
Khi dạy học sinh các thuật toán cơ bản như duyệt đồồ thị ưu tiên chiêồu rộng, duyệt
đồồ thị ưu tiên chiêồu sầu, tìm đường đi ngằến nhầết trên đồồ th ị khồng có chu trình ầm, cầồn
phải nhầến mạnh đêến các sản phẩm của các thuật toán này. Một điêồu rầết thú vị là có rầết
nhiêồu sản phẩm là đồồ thị bộ phận có hướng khồng có chu trình mà tồi tạm g ọi là các đồồ
thị có hướng khồng có chu trình cảm sinh. Có rầết nhiêồu bài tập vêồ đồồ thị trong các kỳ
thi gầồn đầy sử dụng các đồồ thị bộ phận này.
1. DAG đường đi ít cạnh nhấắt
Khi thực hiện duyệt đồồ thị ưu tiên chiêồu rộng (BFS) từ đỉnh s ta gọi d[i] là độ dài
đường đi ít cạnh nhầết từ s đêến i (d[i]= nêếu khồng có đường đi từ s đêến i). Xầy dựng đồồ
thị bộ phận G'=(V',E') như sau:
V' V
E' = {(u,v) E: d[v]=d[u]+1}
Đồồ thị này còn được gọi là đồồ thị đường đi ít cạnh nhầết vì tầết cả các đường đi ngằến
nhầết (theo nghĩa ít cạnh nhầết) đêồu đi qua các cung của đồồ thị này.
Dêỗ dàng nhận thầếy G' là một DAG và đặc biệt, sằếp xêếp topo tự nhiên của nó là sằếp
xêếp theo giá trị d[i] tằng dầồn. Nó cũng chính là thứ tự của các đỉnh khi đưa vào/lầếy ra
khỏi hàng đợi trong phép duyệt BFS (điêồu này khiêến cho ta khồng ph ải th ực hi ện m ột
x , x ..., x p
phép sort đầồy đủ nữa). Chính xác hơn, nêếu gọi 1 2,
là các đỉnh theo thứ tự đưa vào
hàng đợi thì ta có một sằếp xêếp topo trên G'.
Với đồồ thị G' ta có thể xầy dựng một sồế bài toán mở rộng cho BFS như:
Bài toán 3: Hãy tìm đường đi ngằến nhầết (ít cạnh nhầết) từ đỉnh s đêến đỉnh t. Nêếu nh ư có
nhiêồu đường đi như vậy thì tìm đường đi có:
Giá thành nhỏ nhầết/lớn nhầết
Sồế đỉnh đi qua nhiêồu nhầết/ít nhầết
Để giải bài toán 3, trước tiên chúng ta thực hiện BFS để xầy dựng đồồ th ị G' sau đó
trên G' ta giải bài toán tìm đường đi ngằến nhầết/dài nhầết dựa trên sằếp xêếp topo của nó
(bài toán 1)
Bài toán 4: Hãy đêếm sồế đường đi ngằến nhầết từ s đêến t?
Đầy chính là bài toán 2 (đêếm sồế đường đi) trên đồồ th ị G' với một sằếp xêếp topo
Bài tập 4 (VOI 2009):
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.
Yêu cầồu: Cho các sồế nguyên dương n, m, s và m cặp sồế (u, v) xác đ ịnh từ u có th ể kêết nồếi
trực tiêếp tới được v. Hãy xác định sồế lượng trang web ổn định đồếi với s.
Dữ liệu:
Dòng đầồu tiên chứa 3 sồế nguyên n, m và s (2 ≤ 10000, 1 ≤ m ≤ 50000, 1 ≤ s ≤ n).
Mồỗi dòng trong m dòng tiêếp theo chứa 2 sồế nguyên u và v (1 ≤ u, v ≤ n, u ≠ v).
Các sồế trên một dòng được ghi cách nhau ít nhầết một dầếu cách.
Kêết quả: Một sồế nguyên - sồế trang web ổn định đồếi với s.
Bài toán trên là bài toán đêếm các đỉnh có ít nhầết hai đường đi ngằến nhầết từ s.
Phương pháp giải nó là bài toán 4 (với một lưu ý là ta khồng thực sự đêếm mà chỉ cầồn
phần biệt các đỉnh có 0, 1, hơn 1 đường đi ngằến nhầết từ s)
2. DAG đường đi ngắắn nhấắt
Các thuật toán Dijkstra, Ford_bellman tìm đường đi ngằến nhầết từ một đỉnh s đêồu cho
một mảng dist[i] là khoảng cách ngằến nhầết từ đỉnh s đêến đỉnh i (dist[i]= nêếu khồng có
đường đi từ s đêến i). Tương tự như trên, sau khi có mảng dist[i] ta có đồồ thị bộ phận
G'=(V',E') như sau:
V' V
E'={(u,v)E: dist[v]=dist[u]+L(u,v)}
G' cũng là DAG, DAG này là DAG đường đi ngằến nhầết. Nêếu sử dụng thuật toán
Dijkstra thì một sằếp xêếp topo trên DAG này là thứ tự lấắy ra các đỉnh khỏi hàng đợi ưu
tiến, còn nêếu sử dụng Ford_Bellman thì ta phải thực hiện một phép sort trên m ảng dist.
Cũng như DAG đường đi ít cạnh nhầết, chúng ta cũng có một sồế bài toán dựa trên DAG này
giồếng như bài toán 3, bài toán 4. Dưới đầy là một sồế ví dụ điển hình:
Bài tập 5 (VOI 2007):
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.
Trước tiên sử dụng thuật toán Dijkstra chúng ta tìm được DAG đường đi ngằến nhầết.
Một lầồn nữa chú ý rằồng sằếp xêếp topo trên DAG này chính là thứ tự lầếy ra các đỉnh kh ỏi
hàng đợi ưu tiên. Trên DAG đường đi ngằến nhầết này ta giải bài toán tìm nằng l ượng tồếi
thiểu. Kyỗ thuật dùng ở đầy có thể là tìm kiêếm nhị phần và ta đi đêến bài toán c ơ bản "Cho
nằng lượng x, hỏi rằồng với nằng lượng này có thể đi đêến được n hay khồng?" bài toán này
hoàn toàn giải bằồng qui hoạch động.
Bài tập 6 (IOICamp maraton 2006):
Ngày 27/11 tới là ngày tổ chức thi học kỳ I ở trường ĐH BK. Là sinh viên nằm thứ nhầết,
Hiêếu khồng muồến vì đi muộn mà gặp trục trặc ở phòng thi nên đã chuẩn bị khá kyỗ càng.
Chỉ còn lại một cồng việc khá gay go là Hiêếu khồng biêết đi đường nào tới tr ường là nhanh
nhầết.
Thường ngày Hiêếu khồng quan tầm tới vầến đêồ này lằếm cho nên bầy giờ Hiêếu khồng biêết
phải làm sao cả . Bản đồồ thành phồế là gồồm có N nút giao thồng và M con đ ường nồếi các
nút giao thồng này. Có 2 loại con đường là đường 1 chiêồu và đường 2 chiêồu. Đ ộ dài c ủa
mồỗi con đường là một sồế nguyên dương.
Nhà Hiêếu ở nút giao thồng 1 còn trường ĐH BK ở nút giao thồng N. Vì một lộ trình
đường đi từ nhà Hiêếu tới trường có thể gặp nhiêồu yêếu tồế khác như là gặp nhiêồu đèn đỏ ,
đi qua cồng trường xầy dựng, ... phải giảm tồếc độ cho nên Hiêếu muồến biêết là có tầết c ả bao
nhiêu lộ trình ngằến nhầết đi từ nhà tới trường. Bạn hãy lập trình giúp Hiêếu gi ải quyêết bài
toán khó này.
Input
Dòng thứ nhầết ghi hai sồế nguyên N và M.
M dòng tiêếp theo, mồỗi dòng ghi 4 sồế nguyên dương K, U, V, L. Trong đó:
o K = 1 có nghĩa là có đường đi một chiêồu từ U đêến V với độ dài L.
o K = 2 có nghìa là có đường đi hai chiêồu giữa U và V với độ dài L.
Output: Ghi hai sồế là độ dài đường đi ngằến nhầến và sồế lượng đường đi ngằến nhầết. Biêết
rằồng sồế lượng đường đi ngằến nhầết khồng vượt quá phạm vì int64 trong pascal hay long
long trong C++.
Đầồu tiên chúng ta xầy dựng DAG đường đi ngằến nhầết (bằồng thuật toán Dijkstra). Bài
toán qui vêồ bài đêếm sồế đường đi trên DAG này. Đầy chính là bài toán 3
Bài tập 7 (IOICAMP4):
Theo thồếng kê cho biêết mức độ tằng trưởng kinh têế của nước Peace trong nằm 2006 rầết
đáng khả quan. Cả nước có tổng cộng N thành phồế lớn nhỏ được đánh sồế tuầồn tự từ 1
đêến N phát triển khá đồồng đêồu. Giữa N thành phồế này là một mạng lưới gồồm M đường đi
hai chiêồu, mồỗi tuyêến đường nồếi 2 trong N thành phồế sao cho khồng có 2 thành phồế nào
được nồếi bởi quá 1 tuyêến đường. Trong N thành phồế này thì thành phồế 1 và thành phồế N
là 2 trung tầm kinh têế lớn nhầết nước và hệ thồếng đường đảm bảo luồn có ít nhầết m ột
cách đi từ thành phồế 1 đêến thành phồế N.
Tuy nhiên,cả 2 trung tầm này đêồu có dầếu hiệu quá tải vêồ mật độ dần sồế. Vì v ậy, đ ức vua
Peaceful quyêết định chọn ra thêm một thành phồế nữa để đầồu tư thành một trung tầm
kinh têế thứ ba. Thành phồế này seỗ tạm ngưng mọi hoạt động thường nh ật, cũng nh ư mọi
luồồng lưu thồng ra vào để tiêến hành nầng cầếp cơ sở hạ tầồng. Nhưng trong thời gian s ửa
chữa ầếy, phải bảo đảm đường đi ngằến nhầết từ thành phồế 1 đêến thành phồế N khồng b ị thay
đổi, nêếu khồng nêồn kinh têế quồếc gia seỗ bị trì trệ.
Vị trí và đường nồếi giữa N thành phồế được mồ tả như một đồồ thị N đỉnh M cạnh. Hãy giúp
nhà vua đêếm sồế lượng thành phồế có thể chọn làm trung tầm kinh têế th ứ ba sao cho thành
phồế được chọn thỏa mãn các điêồu kiện ở trên
Input
Dòng đầồu tiên ghi 2 sồế nguyên dương N và M là sồế thành phồế và sồế tuyêến đ ường.
Dòng thứ i trong sồế M dòng tiêếp theo ghi 3 sồế nguyên d ương xi, yi và di v ới ý nghĩa
tuyêến đường thứ i có độ dài di và nồếi giữa 2 thành phồế xi, yi.
Output:
Dòng đầồu tiên ghi sồế tự nhiên S là sồế lượng các thành phồế có th ể ch ọn làm trung
tầm kinh têế thứ ba.
S dòng tiêếp theo, mồỗi dòng ghi 1 sồế nguyên dương là sồế th ứ tự c ủa thành phồế đ ược
chọn ( In ra theo thứ tự tằng dầồn )
Một thành phồế được chọn là thành phồế mà khi rút nó ra khỏi đồồ th ị khồng ảnh
hưởng đêến sồế lượng đường đi ngằến nhầết từ 1 đêến n.
Đặt f[u] là sồế lượng đường đi ngằến nhầết từ 1 đêến u và g[u] là sồế lượng đường đi
ngằến nhầết từ u đêến n (hai mảng này có thể tính trên các DAG đường đi ngằến nhầết của đồồ
thị xuồi và đồồ thị ngược). u là thành phồế được chọn khi f[u]*g[u]
- Xem thêm -