atcoder ABC 318 D - General Weighted Max Matchingの勉強

atcoder.jp

・参考
Editorial - THIRD PROGRAMMING CONTEST 2023 ALGO（AtCoder Beginner Contest 318）
「bitDPで巡回セールスマンを解く」の解説がよくわからなかったのでさらに解説【python実装】 - Qiita
bitDP（集合を用いたDP）について - D言語で競プロ

・説明
　参考記事の1つ目をPythonで実装した。この問題はbitDPを使って解く。bitDPについては参考記事2，3を参考にした。
　集合bに含まれていない頂点を追加してDPを更新していく。コードの説明は下の実装でコメントアウトしている。

n=int(input())
d=[[0 for _ in range(n)]for _ in range(n)]

for i in range(n-1):
    l=list(map(int,input().split()))
    for j in range(i+1,n):
        d[i][j]=d[j][i]=l[j-i-1]  
        
dp=[0 for _ in range(2**n)]
#print(dp)
for b in range(2**n-1):   #辺を貼る選んだ頂点のbという集合。
    l=-1
    for i in range(n):
        if not (b>>i)&1:   #b>>i&1==0と同じ。 b&(1<<i)と同じ。iがbに含まれていない。例えばb=2(0b10)はi=1のとき、1<<i=2**1=2=0b10よりこのとき含まれる。
            l=i   #まだbに含まれていない最小の頂点の番号をl.
            break
        
    for i in range(n):
        if not (b>>i)&1:   #bがiに含まれていなかったら.
            nb=b | (1<<l) | (1<<i)  #頂点l, iをbに追加する。https://qiita.com/karutetto332/items/90fc8186c915afd1e9e8  参照。
            dp[nb]=max(dp[nb], dp[b]+d[l][i])

print(dp[2**n-1])