Overview

This is a problem of selecting a combination of projects that maximizes profit, subject to budget constraints and conflict relationships between projects.

Analysis

This problem is a combinatorial optimization problem of “which projects to select.” A naive approach is to try all subsets (combinations) of projects. Since the number of projects \(N\) is at most \(18\), the number of subsets is \(2^{18} = 262144\), which is small enough for exhaustive search.

For each subset, we check:

1. Does the total cost exceed the budget \(K\)?
2. Does the subset contain any pair of conflicting projects?

Among the subsets that satisfy these conditions, we find the one with the maximum total profit.

Since conflict relationships are given as \(M\) pairs, we select two projects from the chosen project list and check whether they are in the conflict list. Python’s itertools.combinations is convenient for this.

To efficiently check for conflicts, we can store the conflict information in a set as tuples (u, v) (where \(u < v\)), enabling fast existence checks.

Algorithm

1. Generate all subsets of projects using bitmask enumeration (\(2^N\) subsets).
2. For each subset, check the following:
   • Is the total cost within the budget \(K\)?
   • Are there no conflicting pairs among the selected projects?
3. Record the maximum profit among subsets that satisfy the conditions.

Complexity

• Time complexity: \(O(2^N \cdot N^2)\)
  • Number of subsets: \(O(2^N)\)
  • For each subset, the number of selected projects is at most \(N\), and the number of pairs chosen from them is at most \(O(N^2)\)
• Space complexity: \(O(M + N)\)
  • \(O(M)\) for the set storing conflict information, \(O(N)\) for the cost and profit arrays

Implementation Notes

• Project indices are given as 1-based in the input, but are converted to 0-based for internal processing.

• By normalizing conflict information to the form (u, v) (where \(u < v\)), we ensure correct matching regardless of order.

• Using itertools.combinations makes it easy to generate pairs of selected projects.

  Source Code

from itertools import combinations

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    K = int(data[idx]); idx += 1
    
    C = [0] * N
    P = [0] * N
    for i in range(N):
        C[i] = int(data[idx]); idx += 1
        P[i] = int(data[idx]); idx += 1
        
    conflicts = set()
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        u -= 1
        v -= 1
        if u > v:
            u, v = v, u
        conflicts.add((u, v))
        
    max_profit = 0
    
    # 全ての部分集合を試す (bit全探索)
    for mask in range(1 << N):
        cost = 0
        profit = 0
        selected = []
        for i in range(N):
            if mask & (1 << i):
                cost += C[i]
                profit += P[i]
                selected.append(i)
        if cost > K:
            continue
            
        # 選んだプロジェクト間に競合がないかチェック
        valid = True
        for u, v in combinations(selected, 2):
            if u > v:
                u, v = v, u
            if (u, v) in conflicts:
                valid = False
                break
        if valid:
            if profit > max_profit:
                max_profit = profit
                
    print(max_profit)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.