私がここで尋ねようとしている質問は、スタックオーバーフローの前にすでに尋ねられています。しかし、 Skiminokによって投稿された解決策を正しく理解することはできません。
これがリンクです。
上記のリンクに掲載されている2つのサンプルテストケースを使用して解決策を試しましたが、正しい答えを得ることができません。
テストケースの場合1::
N=3およびK=2
5 4 7
DAGは次のようになります::
注：上記のDAGを作成しました。
piとpjを2つの異なる問題とします。次に、同じ日のpiの直後にpjを連続して解くことができる場合に限り、piからpjに有向エッジを描画します。つまり、次の条件を満たす必要があります。
i <jです。これは、それほど難しくない問題を早期に解決する必要があるためです。
| vi --vj | > = K（評価要件）。
次に、次のことを考慮して2部グラフを作成しました。
元のDAGの各有向エッジ（u、v）について、無向エッジ（au、bv）を2部グラフに追加する必要があります。ここで、{ai}と{bi}はサイズnの2つの部分です。
答え=上記の2部グラフでの最大カーディナリティマッチング。
上記の2部グラフでの最大カーディナリティマッチング=1（緑色のegde）
しかし、答えは2です。
同様にサンプルテストケース2：
5 1
5 3 4 5 6
上のグラフのMAxカーディナリティは複数ですが、正解は1です。
私はそれを正しく実装していないと思います、私がどこで間違いを犯しているのか教えてくださいまたは他の方法はありますか
ありがとう！