C - グラフいじり
Editorial
/


Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 800 点
問題文
N 頂点 M 辺の有向グラフが与えられます。 頂点には 1, 2, ..., N と番号が付いており、 i 番目の辺は頂点 a_i から頂点 b_i へ張られる、長さ c_i の辺です。 また、このグラフは強連結、つまりすべての i, j(1 ≦ i, j ≦ N) について、 頂点 i から頂点 j へのパスが存在します。
あなたはこのグラフの辺を 1 本だけ選び、長さを好きに変える事が出来ます。 なお、元の長さと同じ長さにしても良いです。
グラフを、どのサイクルを選んでも長さが 0 となるようにできるかを判定してください。
グラフから 2 本以上辺を選んだ時(辺を M 本、d_1, d_2, ..., d_M 番目の辺を選んだとします)、以下の条件を満たすならば、この選んだ辺たちをグラフのサイクルと呼びます。
- i = 1, 2, ..., M-1 について、b_{d_i} = a_{d_{i+1}}
- a_{d_1} = b_{d_M} (11:26)修正しました
- i ≠ j ならば、a_{d_i} ≠ a_{d_j} (11:22)修正しました
サイクルの長さとは、選んだ辺たちの長さの総和の事を指します。
制約
- 入力は全て整数
- 2 ≦ N ≦ 300
- 1 ≦ M ≦ N^2 - N
- 1 ≦ a_i, b_i ≦ N
- |c_i| ≦ 10^9
- a_i ≠ b_i
- すべての 1 ≦ i, j ≦ M について、i ≠ j ならば a_i ≠ a_j もしくは b_i ≠ b_j
- 与えられるグラフは強連結、つまりすべての 1 ≦ i, j ≦ N について、頂点 i から頂点 j へのパスが存在する
入力
入力は以下の形式で標準入力から与えられる。
N M a_1 b_1 c_1 a_2 b_2 c_2 : a_M b_M c_M
出力
グラフを、どのサイクルを選んでも長さが 0 となるようにできるならば Yes
、できないならば No
と出力してください。
入力例 1
3 3 1 2 1 2 3 2 3 1 3
出力例 1
Yes
どれかの辺の長さを 1+2+3 = 6 減らせばよいです。
入力例 2
4 5 1 2 1 2 3 2 3 1 2 2 4 3 4 1 3
出力例 2
No
入力例 3
4 5 1 2 1 2 3 -2 3 1 2 2 4 -3 4 1 3
出力例 3
Yes
1 番目の辺の長さを 0 にすればよいです。