Tài liệu Bồi dưỡng học sinh giỏi môn tin học thpt chuyên đề qui hoạch động trên đồ thị có hướng, không chu trình

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 -