No.3699 Poaching Negotiations
タグ : / 解いたユーザー数 27
作問者 :
yuki2006
Problem Statement
$N$ participants are to be divided into $2$ teams, Team Ko and Team Otsu. Putting participant $i$ in Team Ko yields a profit of $a_i$, and putting them in Team Otsu yields a profit of $b_i$.
In addition, there are $M$ pairs of close friends, and if the $j$-th pair $(u_j, v_j)$ is split into different teams, a loss of $c_j$ is incurred. Find the maximum value of the total profit obtained minus the total loss.
Input
$N\ M$ $a_1\ b_1$ $\vdots$ $a_N\ b_N$ $u_1\ v_1\ c_1$ $\vdots$ $u_M\ v_M\ c_M$
$1 \le N \le 500$
$0 \le M \le 5000$
$0 \le a_i, b_i \le 10^6$
$1 \le u_j < v_j \le N$
$0 \le c_j \le 10^6$
All input values are integers.
Output
Output the maximum value of the total profit minus the total loss. Print a newline at the end.
Sample
Sample 1
Input
3 2 5 1 1 5 3 3 1 2 1 2 3 1
Output
12
If participant $1$ is put in Team Ko and participants $2, 3$ are put in Team Otsu, the profit is $5 + 5 + 3 = 13$, and the only loss is $1$ from the pair $(1, 2)$, which ended up on different teams. Thus the value is $13 - 1 = 12$, which is the maximum. If everyone is put in Team Ko, the loss is $0$, but the profit is only $5 + 1 + 3 = 9$.
Sample 2
Input
2 1 10 0 0 10 1 2 100
Output
10
Splitting them into different teams gives $10 + 10 - 100 = -80$. Putting both $2$ people in Team Ko gives $10 + 0 = 10$, and putting both $2$ people in Team Otsu gives $0 + 10 = 10$, so $10$ is the maximum.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。