2016-10-20 5 views
-2

私はこのような問題に対して最も速いアルゴリズムを必要とします。私はここでグラフを使うべきだと思う。 これはコーディングではなくアルゴリズムです。2つの要素の融合のためのグラフ理論の使用

基本的に、2つの要素のリストが与えられています。これらの2つのリストはalpha-Listとnum-Listです。次に、各要素が融合可能な融合リストの融合リストも与えられます。 alpha-Listとnum-Listのいずれかの要素を組み合わせることによって可能な融合の最大数を見つけることが目的です。組み合わせが融合リストに存在する場合にのみ、これら2つの要素を融合することができます。

制約:alpha-Listとnum-Listの各要素は、1回だけ融合できます。いずれの要素も、それ自身のリストの要素と融合することはできません。融合は、融合が融合リストに記載されている場合にのみ可能です。

例:

アルファリスト{A、B、C、D} NUM-リスト{1、2、3、4}

融合リスト{(1)、( 、2)、(4)、(B、4)、(D、3)}

出力:最大の可能な融合は - 3

+3

[2人の組が互いに結婚するための最速アルゴリズム]の可能な複製(http://stackoverflow.com/questions/40105764/fastest-algorithm-for-set-of-two-people-to-marry-eachother) ) –

+1

**昨日** ... –

+0

多くの助けがありませんでした。 – HumparDumpar

答えて

0

それは二部グラフにおける単純なマッチング問題であり、たとえばwikiを参照してください。頂点の最初のセットはalpha-Listであり、2番目のものはnum-Listであり、エッジはfusion-Listです。

関連する問題