結果

問題 No.3201 Corporate Synergy
ユーザー ooaiu
提出日時 2025-07-11 22:23:36
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 892 bytes
コンパイル時間 1,529 ms
コンパイル使用メモリ 81,996 KB
実行使用メモリ 67,044 KB
最終ジャッジ日時 2025-07-11 22:23:40
合計ジャッジ時間 3,431 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 2
other RE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

from pulp import *

N = int(input())
P = list(map(int, input().split()))
M = int(input())
E = []
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    E.append([a, b])

K = int(input())
ABS = [list(map(int, input().split())) for i in range(K)]
a, b, S = zip(*ABS)
A = [i - 1 for i in a]
B = [i - 1 for i in b]


prob = LpProblem(sense=LpMaximize)

x = [LpVariable(f"x{i}", 0, 1, LpBinary) for i in range(N)]
y = [LpVariable(f"y{i}", 0, 1, LpBinary) for i in range(K)]

prob += lpSum(P[i] * x[i] for i in range(N)) + lpSum(S[i] * y[i] for i in range(K))

for a, b in E:
    prob += x[b] <= x[a]


for i in range(K):
    prob += y[i] <= x[A[i]]
    prob += y[i] <= x[B[i]]

prob.solve(pulp.PULP_CBC_CMD(msg=False))

ans = 0
for i in range(N):
    if x[i].value() == 1:
        ans += P[i]

for i in range(K):
    if y[i].value() == 1:
        ans += S[i]

print(ans)
0