結果

問題 No.3201 Corporate Synergy
コンテスト
ユーザー pitP
提出日時 2025-07-11 23:20:15
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 1,089 bytes
コンパイル時間 612 ms
コンパイル使用メモリ 12,032 KB
実行使用メモリ 11,264 KB
最終ジャッジ日時 2025-07-11 23:20:17
合計ジャッジ時間 2,458 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 2
other RE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import pulp

N = int(input())
P = list(map(int, input().split()))
M = int(input())
U, V = [-1] * M, [-1] * M
for i in range(M):
    U[i], V[i] = map(lambda x: int(x) - 1, input().split())
K = int(input())
A, B, S = [-1] * K, [-1] * K, [-1] * K
for i in range(K):
    A[i], B[i], S[i] = map(int, input().split())
    A[i] -= 1
    B[i] -= 1

# https://tombo314.hatenablog.com/entry/2024/08/02/130633
prob = pulp.LpProblem(sense=pulp.LpMaximize)

# x = [pulp.LpVariable(f"x{i}", cat=pulp.LpBinary) for i in range(N)]
x = [pulp.LpVariable(f"x{i}", lowBound=0, upBound=1, cat=pulp.LpBinary) for i in range(N)]

for i in range(M):
    prob.addConstraint(x[V[i]] <= x[U[i]])

objective = 0
for i in range(N):
    objective += x[i] * P[i]
for i in range(K):
    objective += S[i] if (x[A[i]] == 1) and (x[B[i]] == 1) else 0
prob += objective

# print(objective)
prob.solve(pulp.PULP_CBC_CMD(msg=False))

ans = 0
for i in range(N):
    # print(i, x[i].value())
    if x[i].value():
        ans += P[i]
for i in range(K):
    if x[A[i]].value() and x[B[i]].value():
        ans += S[i]

print(ans)
0