b992: 欸肥宅快去運動啦!
Tags : 圖論
Accepted rate : 5人/9人 ( 56% ) [非即時]
評分方式:
Strictly

最近更新 : 2017-12-16 07:14

Content

sayori

你是個成天待在家看動畫打遊戲的肥宅,但比其他肥宅幸運的是,你有一個天然可愛的幼馴染。有天你的幼馴染不知道發了什麼神經,堅持你要出門運動跑個幾圈,理由是擔心你以後會變成繭居尼特。你只好翻出你的地圖,找出裡面的$n$個路口和$m$條連接兩個路口的單向道路。對於第$i (1 \leq i \leq m)$條單向道路,你已經根據路況算出「跑完這段單向道路所消耗的大卡數」$c_i$。注意$c_i$可能小於$0$,代表單向道路$i$上有賣食物,讓你跑完後還變肥。由於你只是在敷衍你的幼馴染,並不想認真運動,你打算在這張地圖上找一個簡單環(亦即路口皆不重複的環),使得跑完一圈所消耗的大卡數總和最小。

Input

輸入的第一行是一個正整數$T$,代表接下來有$T$筆測試資料。

每筆測試資料的第一行有兩個整數$n, m$,代表地圖上有$n$個路口以及連接其中兩個路口的$m$條單向道路。

接下來的$m$行,第$i$行有三個整數$u_i, v_i, c_i$,代表有一條單向道路連接路口$u_i$到路口$v_i$,且沿著這條單向道路從路口$u_i$跑到路口$v_i$會消耗$c_i$大卡的熱量。

所有的測資檔皆滿足

  • $T \leq 10$
  • $1 \leq n \leq 5000$,$0 \leq m \leq 200000$,且$0 \leq mn \leq 10^8$
  • $1 \leq u_i, v_i \leq n$,且$u_i \neq v_i$
  • $-10^6 \leq c_i \leq 10^6$
Output

對於每筆測試資料,輸出一行。如果地圖上根本沒有環,輸出"INF"(不含引號)。如果地圖上存在一個跑完後會讓你變肥的簡單環,輸出"-1"(不含引號)。如果地圖上存在簡單環,但沒有一個會讓你變肥,輸出一個非負整數$c^*$,代表跑完一個地圖上的簡單環,所消耗的熱量最小值。

Sample Input
3
4 5
1 2 1
2 3 1
3 1 2
3 4 -1
4 1 4
3 3
1 3 -5
1 3 5
3 2 -10
4 3
1 2 -1
2 3 -1
3 2 -1
Sample Output
4
INF
-1
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (80%): 10.0s , <10M
不公開 測資點#1 (20%): 1.0s , <10M
Hint :
  1. 這題可以做到完美的$O(mn)$ 我也已經盡力讓$O(mn\log n)$的演算法TLE了
    但如果最後你還是用$O(mn\log n)$的演算法AC 我也沒辦法了QAQ
  2. 醒醒吧你沒有幼馴染
Tags:
圖論
出處:
經典問題 [管理者:
xavier13540 (柊 四千)
]


ID User Problem Subject Hit Post Date
13116
xavier13540 (柊 四千)
b992
O(mn)演算法
398 2017-12-11 05:49