私はここで割り当て問題への解決策を通じて読んでいた「割当問題」解決の質問

Question

：http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm

私はO（N3）ソリューションを理解する）が、簡単にO（N4）ソリューションについての質問がありました。

おそらく私は表記法を誤解しましたが、手順2で重みを変更すると、なぜw1-> j2の重みはw2-> j1の増加と同じように増加しません。

は、誰もがより良い二つの論理シンボルがあること「と」それぞれ「XOR」になっているように見えます

Answer 1

で定義されたルール内の表記を説明することができます。選択されたxorシンボルは包括的であるか、おそらくタイプミスです。あまり混乱させない選択肢については、http://en.wikipedia.org/wiki/Exclusive_orを参照してください。この解釈と

、次のような可能性があります。

1. iもjVでもされていないが。その後、最初のケースが得られます。
2. iはVであるが、jではない。次に、あなたは2番目のケースを取得します。
3. iはVにはありませんが、jです。次に、あなたは2番目のケースを取得します。
4. iおよびjはいずれもVです。次に、3番目のケースを取得します。

ご覧のとおり、すべてのケースがカバーされており、あいまいさはありません。