概要

\(N \leq 18\) と小さいことを利用して、選ぶプロジェクト集合をビットで表し、競合しない（独立集合）かどうかと予算・利益を全探索して最大利益を求めます。

考察

• この問題は「予算 \(K\) 以内で利益最大」という点だけ見るとナップサック問題ですが、ここには「競合する2つを同時に選べない」という制約（グラフの独立集合制約）が加わっています。
• \(K \leq 10^5\) なので、素朴に「予算を添字にしたDP（\(O(NK)\)）」を作っても、競合制約の扱いが難しく（状態に“どの頂点を選んだか”が必要になりがち）、そのままでは解けません。
• 一方で \(N \leq 18\) なので、全ての選び方は \(2^N \leq 262144\) 通りしかありません。
  よって「全ての部分集合を調べる」方針が現実的です。
• ただし、各部分集合について毎回「競合がないか」を辺ごとに確認すると、実装次第では \(O(2^N \cdot M)\) のようになり無駄が出ます。
  そこで、集合を1要素ずつ増やしながら「直前の集合が独立集合なら、新しく足した1要素が競合しないかだけ見ればよい」という形にします。

アルゴリズム

1. 競合関係をグラフとみなし、各プロジェクト \(i\) について
   「\(i\) と競合する頂点集合」をビット集合 adj[i] として持ちます。
   • 例：adj[i] の \(j\) ビット目が 1 なら、\(i\) と \(j\) は同時に選べない。
2. 部分集合 \(s\)（\(0\) 〜 \(2^N-1\)）をビットで表します。
   • \(s\) の \(i\) ビット目が 1 ⇔ プロジェクト \(i\) を選ぶ。
3. 各部分集合について以下をDP的に更新します。
   • cost[s]：集合 \(s\) の総コスト \(\sum C_i\)
   • profit[s]：集合 \(s\) の総利益 \(\sum P_i\)
   • ind[s]：集合 \(s\) が競合を含まない（独立集合）なら True
4. 遷移の作り方：
   • \(s\) の最下位の 1 ビット（lsb）を取り、その要素を \(i\) とする
     （i = lsb.bit_length() - 1）。
   • prev = s ^ lsb とすると、\(s\) は prev に \(i\) を1つ足した集合です。
   • まず和は必ず作れるので
     • cost[s] = cost[prev] + C[i]
     • profit[s] = profit[prev] + P[i]
   • 独立集合判定は次で十分です：
     • ind[prev] が True（prev が独立集合）
     • かつ prev と adj[i] が交わらない（= \(i\) と競合する頂点を prev が含まない）

          - ビット演算で `(prev & adj[i]) == 0`
       

     • これなら ind[s] = True
5. ind[s] が True かつ cost[s] <= K のとき profit[s] で答えを更新します。

このように、各集合 \(s\) の判定が「1個足した要素 \(i\) との競合チェックだけ」になるため、効率よく全探索できます。

計算量

• 時間計算量: \(O(2^N)\)
  （各部分集合につき、最下位ビット取得・加算・AND判定など定数時間）
• 空間計算量: \(O(2^N)\)
  （cost, profit, ind の配列）

実装のポイント

• 競合関係は隣接リストではなく ビット集合 adj[i] にすると、競合チェックが (prev & adj[i]) == 0 の1回で済みます。

• 部分集合 \(s\) をそのまま使って毎回合計を計算すると \(O(N)\) かかるため、prev からの差分で cost/profit を更新しています。

• lsb = s & -s（最下位の1ビット）と bit_length() を使うと、追加した要素 \(i\) を高速に特定できます。

  ソースコード

import sys

def main():
    it = list(map(int, sys.stdin.buffer.read().split()))
    if not it:
        return
    pos = 0
    N = it[pos]; M = it[pos+1]; K = it[pos+2]
    pos += 3

    C = [0] * N
    P = [0] * N
    for i in range(N):
        C[i] = it[pos]
        P[i] = it[pos+1]
        pos += 2

    adj = [0] * N
    for _ in range(M):
        u = it[pos] - 1
        v = it[pos+1] - 1
        pos += 2
        adj[u] |= 1 << v
        adj[v] |= 1 << u

    size = 1 << N
    cost = [0] * size
    profit = [0] * size
    ind = [False] * size
    ind[0] = True

    ans = 0
    for s in range(1, size):
        lsb = s & -s
        i = lsb.bit_length() - 1
        prev = s ^ lsb

        cost_s = cost[prev] + C[i]
        profit_s = profit[prev] + P[i]
        cost[s] = cost_s
        profit[s] = profit_s

        if ind[prev] and (prev & adj[i]) == 0:
            ind[s] = True
            if cost_s <= K and profit_s > ans:
                ans = profit_s

    print(ans)

if __name__ == "__main__":
    main()

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