概要

通路で直接つながる区画を同時に選べない（独立集合）という制約の下で、選んだ区画の容量和を最大化し、最後に \(M\) で上限をかける問題です。

考察

• 「選んだ区画同士が辺でつながっていない」という条件は、グラフ理論でいう独立集合 (independent set) です。
  よって本質は「重み付き最大独立集合（各頂点の重みが \(P_i\)）」を求めることになります（最後に \(M\) を超えないように \(\min(\cdot, M)\) を取る）。

• 素朴に「すべての部分集合を試す」と \(2^N\) 通りで、\(N \le 40\) でも
  \(2^{40} \approx 10^{12}\) となり到底間に合いません（TLE）。

• そこで \(N \le 40\) という制約から典型解法の 半分全列挙 (Meet-in-the-Middle) を使います。
  頂点を前半 \(A\) と後半 \(B\) に分け、各半分は最大 20 頂点なので \(2^{20} \approx 10^6\) 程度まで落とせます。

• ただし、\(A\) の選び方に応じて「\(B\) で選べない頂点（\(A\) と辺でつながる頂点）」が変わります。
  これを高速に処理するために、\(B\) 側は「許された頂点集合（マスク）の中で作れる独立集合の最大重み」を前計算しておきます。

アルゴリズム

以下、頂点集合を前半 \(A\)（サイズ \(n_1\)）、後半 \(B\)（サイズ \(n_2\)）に分割します（\(n_1=\lfloor N/2\rfloor\)）。

1. ビットマスクでグラフを表す

• 各頂点 \(i\) について、隣接頂点集合をビットマスク adj[i] で持ちます。
• \(A\) 内の隣接（adjA[i]）、\(B\) 内の隣接（adjB[j]）、そして \(A\) の頂点が \(B\) のどの頂点とつながるか（crossA[i]）を用意します。

2. 後半 \(B\) の全列挙：独立集合の重み weightB

• \(B\) の部分集合 \(m\)（\(0 \le m < 2^{n_2}\)）について、
  • weightB[m] = -1（不可能）または独立集合ならその容量和 をDP的に求めます。
• 求め方：\(m\) の最下位ビット lsb を取り、その頂点 \(v\) を追加できるか
  • 直前集合 prev = m ^ lsb が独立で
  • さらに \(v\) が prev のどの頂点とも隣接していない（(adjB[v] & prev) == 0） なら weightB[m] = weightB[prev] + P[v] とします。

3. 「許された集合の中での最大値」を作る（部分集合DP）

後で \(A\) の選択によって「\(B\) で使ってよい頂点集合（allowed）」が毎回変わるので、次を作ります：

• best[mask] = 「mask の部分集合のうち、独立集合になっているものの重み最大値」

手順： 1. まず best[m] = max(best[m], weightB[m]) を入れる（独立集合だけ正の値が入る）。 2. 次に典型的な subset DP を行い、
best[mask] = max(best[mask], best[mask without one bit]) を全ビットについて伝播します。
これにより任意の allowed に対し best[allowed] が \(O(1)\) で取れます。

4. 前半 \(A\) の全列挙：独立集合と「\(B\) 側の禁止集合」

• \(A\) の部分集合 \(m\) について
  • weightA[m] = \(A\) 内で独立なら容量和、無理なら -1
  • forb[m] = 「\(m\) に含まれる頂点と辺でつながる \(B\) 側頂点」の集合（ビットマスク） を同様にDPで求めます。
• \(m\) が独立であれば、\(B\) 側で使える集合は
  allowed = allB ^ forb[m]（allB は \(B\) 全頂点のマスク）
  となり、最大合計は
  $\( \text{weightA}[m] + \text{best}[\text{allowed}] \)$ で求まります。

5. 最後に \(M\) で上限をかける

問題文より保管総量は \(M\) を超えられないので、答えは $\( \min(\text{最大容量和},\, M) \)$ です。

計算量

• 時間計算量:
  
  • \(B\) の独立集合判定DP：\(O(2^{n_2})\)（各状態で定数回のビット演算）
    
  • subset DP：\(O(n_2 \cdot 2^{n_2})\)
    
  • \(A\) のDPと合成：\(O(2^{n_1})\)
    よって全体で
    $\( O\big((n_2+1)2^{n_2} + 2^{n_1}\big) = O\big(N \cdot 2^{N/2}\big) \)$
• 空間計算量:
  weightB, best が \(O(2^{n_2})\)、weightA, forb が \(O(2^{n_1})\) なので
  $\( O(2^{N/2}) \)$

実装のポイント

• ビットマスクで隣接を持つと、「隣接があるか」の判定が (adj[v] & subset) == 0 の1回で済み高速です。

• best[allowed] を毎回作り直すと間に合わないため、subset DPで前計算して \(O(1)\) 参照にします。

• Pythonでは配列が大きくなるので、list より省メモリな array('q')（64bit整数）や array('I')（32bit）を使うと安定します。

• 入力は sys.stdin.buffer.read() でまとめて読み、イテレータで回すと高速です。

  ソースコード

import sys
from array import array

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    M = next(it)
    K = next(it)
    P = [next(it) for _ in range(N)]

    adj = [0] * N
    for _ in range(K):
        u = next(it) - 1
        v = next(it) - 1
        adj[u] |= 1 << v
        adj[v] |= 1 << u

    n1 = N // 2
    n2 = N - n1
    maskA = (1 << n1) - 1
    maskB = (1 << n2) - 1

    PA = P[:n1]
    PB = P[n1:]

    adjA = [0] * n1
    crossA = [0] * n1
    for i in range(n1):
        a = adj[i]
        adjA[i] = a & maskA
        crossA[i] = (a >> n1) & maskB

    adjB = [0] * n2
    for j in range(n2):
        orig = n1 + j
        adjB[j] = (adj[orig] >> n1) & maskB

    sizeB = 1 << n2
    weightB = array('q', [-1]) * sizeB
    weightB[0] = 0
    for m in range(1, sizeB):
        lsb = m & -m
        v = lsb.bit_length() - 1
        prev = m ^ lsb
        w = weightB[prev]
        if w >= 0 and (adjB[v] & prev) == 0:
            weightB[m] = w + PB[v]

    best = array('q', [0]) * sizeB
    for m in range(sizeB):
        w = weightB[m]
        if w > 0:
            best[m] = w

    for i in range(n2):
        bit = 1 << i
        for m in range(sizeB):
            if m & bit:
                other = m ^ bit
                bo = best[other]
                if bo > best[m]:
                    best[m] = bo

    sizeA = 1 << n1
    weightA = array('q', [-1]) * sizeA
    forb = array('I', [0]) * sizeA
    weightA[0] = 0
    for m in range(1, sizeA):
        lsb = m & -m
        v = lsb.bit_length() - 1
        prev = m ^ lsb
        w = weightA[prev]
        if w >= 0 and (adjA[v] & prev) == 0:
            weightA[m] = w + PA[v]
            forb[m] = forb[prev] | crossA[v]

    ans = 0
    allB = maskB
    for m in range(sizeA):
        w = weightA[m]
        if w >= 0:
            allowed = allB ^ forb[m]
            total = w + best[allowed]
            if total > ans:
                ans = total

    if ans > M:
        ans = M
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。