http://www.lydsy.com/JudgeOnline/problem.php?id=1050
表示被暴力嚇到了orz
我竟然想不到。。。我竟然還想到分數規劃，，但是不可做。。。然后又想到最小生成樹，，然后不會做orz
我一直在糾結怎么最大化（或最小化）分母和最小化（或最大化）分子的做法。。。。。但是。。。。不會orz
沒想到是暴力orz
直接排序后枚舉最小的邊，生成樹后要最大的邊最小（排序后即可orz），然后更新答案即可。
但是不知道之前寫錯了啥wa了兩發，，，隨便改改才過orz
?
?
?
Description
給你一個無向圖，N(N<=500)個頂點, M(M<=5000)條邊，每條邊有一個權值Vi(Vi<30000)。給你兩個頂點S和T，求一條路徑，使得路徑上最大邊和最小邊的比值最小。如果S和T之間沒有路徑，輸出”IMPOSSIBLE”，否則輸出這個比值，如果需要，表示成一個既約分數。 備注： 兩個頂點之間可能有多條路徑。
Input
第一行包含兩個正整數，N和M。 下來的M行每行包含三個正整數：x，y和v。表示景點x到景點y之間有一條雙向公路，車輛必須以速度v在該公路上行駛。 最后一行包含兩個正整數s，t，表示想知道從景點s到景點t最大最小速度比最小的路徑。s和t不可能相同。
Output
如果景點s到景點t沒有路徑，輸出“IMPOSSIBLE”。否則輸出一個數，表示最小的速度比。如果需要，輸出一個既約分數。
Sample Input
4 2
1 2 1
3 4 2
1 4
【樣例輸入2】
3 3
1 2 10
1 2 5
2 3 8
1 3
【樣例輸入3】
3 2
1 2 2
2 3 4
1 3
Sample Output
IMPOSSIBLE
【樣例輸出2】
5/4
【樣例輸出3】
2
HINT
?
?
Source
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
