亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

【BZOJ】1050: [HAOI2006]旅行comf(暴力+并查

系統 1673 0

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

【樣例輸入1】
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

【樣例輸出1】
IMPOSSIBLE
【樣例輸出2】
5/4
【樣例輸出3】
2

HINT

?

【數據范圍】

1< ?N < = 500

1 < = x, y < = N,0 < v < 30000,x ≠ y

0 < M < =5000

?

Source

?

?

【BZOJ】1050: [HAOI2006]旅行comf(暴力+并查集)


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 婷婷尹人香蕉久久天堂 | 亚洲国产精品一区二区第四页 | 日本一区二区在线播放 | 奇米线在人线免费视频 | 中文字字幕乱码视频 | 日韩国产欧美成人一区二区影院 | 欧美激情xxxx性bbbb | 老司机精品视频个人在观看 | 久久的爱久久久久的快乐 | 性生活视频免费观看 | 99热这里只有精品1 99热这里只有精品18 | 在线看福利视频120秒 | 四虎影业| 波多野结衣一区二区三区 | 天天撸夜夜操 | 一区二区三区精品视频 | 成人短视频在线观看 | 久久精品美女 | 欧美高清视频www夜色资源网 | 成人禁在线观看午夜亚洲 | 男人的天堂222eee | 婷婷在线成人免费观看搜索 | 亚洲精品欧美精品 | 一区二区三区日韩 | 国产婷婷色综合成人精品 | 国内欧美一区二区三区 | 中文字幕在线不卡精品视频99 | 久久99视频 | 欧美不卡视频在线 | 亚洲日韩精品欧美一区二区一 | 国产99福利视频在线 | 成人欧美一区二区三区在线 | 婷婷亚洲综合 | 91精品国产91热久久p | 99视频九九精品视频在线观看 | 成人一区视频 | 青青青青啪视频在线观看 | 老子影院午夜伦不卡不四虎卡 | 亚洲男人的天堂久久香蕉网 | 香蕉视频一级片 | 另类 欧美 视频二区 |