最大重量の二部マッチング

Question

長方形のグリッド、つまりnノードと2Nエッジの形のグラフがあり、すべての隣接するノードが接続されています。これは、それが2色であることを意味します。したがって、それについて二部マッチングを行うことが可能です。

それぞれ（無向）エッジには、-2、-1、0、1、または2のいずれかの重量が割り当てられています。他の値は許可されていません

マッチングの計量の合計を最大化するこのグラフのマッチングを見つけるにはどうすればよいですか？ Pseudocodeはいいことです。特定の言語を気にしないでください。

理想的には、最悪の場合、2次時に実行されるアルゴリズムを探しています。

---

解決策を提案する前に、私は重量2のエッジ、次に重量1のエッジを使用して最大一致を実行しようとしました（重量2のエッジを越えずに）。私はこの実装で98％を獲得しました（問題は情報学のオリンピックからのものです）、100％の解決策は何だと思っています。

Answer 1

なぜあなたが分間をカットすることを考えているのかわからない。この場合、カットはあなたに一致することを保証されていません。あなたがする必要があるのは、割り当ての問題を解決することです。割り当ての問題. 。連続した最短数学アルゴリズムは、O（ev log v）でそれを解決します。