週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

この間のGoldberg-Tarjanの実装バグを特定しました。 実装として活性頂点をキューで保持していて、そのキューに終点が紛れ込んだのが原因でした。 始点と終点は活性ではないはずですが、間違えて活性として扱ってしまったため終点からフローをすべて始点に戻して流量が0になっていました。

もともと、始点と終点はキューから除外していました。 flow pushして頂点をキューに追加する際に、頂点が始点や終点でないのを確認していました。しかし、初期条件での活性点を追加するところではチェックを忘れていました。初期条件での活性点は始点から枝一本でたどれる頂点なので、つまり始点と終点とが直接つながっているとこのバグを踏みます。pkuの1459番のデータにはそういうものはないので、バグを踏まずacceptされていました。

スポンサーサイト
コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/347-59a351a9
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。