読者です 読者をやめる 読者になる 読者になる

負閉路の検出

pku 3259
グラフが疎な時は、ベルマンフォードを使ったほうが良い
ベルマンフォードのアルゴリズムでは、始点sが現れるのはd[s]=0の初期化だけなので、全体に負閉路があるかどうかはd[i]=0(0<=i< n)とすればできます(蟻本に書いてあるよね)

一般に点集合Sからたどり着ける場所に負閉路があるかは普通d[i]=0(i∈S)でいいはず