38 . 分隊問題
TopCoder
Tags
Description
做為一個邪惡的國際內卷競賽主辦方，你要幫進入複賽的參賽者分隊。
進入複賽的總共有 $N$ 人，每個參賽者由 $1$ 編號到 $N$ 。你將會選擇兩個人，編號 $S$ 和 $T$，任命他們當「內卷大隊長」，並把所有的參賽者分成兩隊。兩個內卷大隊長要在不同隊，每個參賽者都要在其中一隊，但兩隊的人數沒有其他限制。
這些參賽者之中有些人互相認識，而兩個認識的人之間會形成一組「內卷關係」，意味著一個人看到另一個認識的人在卷的話會變卷多少。這 $N$ 個參賽者之間總共有 $M$ 組內卷關係，而第 $i$ 組內卷關係可以由三個正整數 $u_i, v_i, c_i$ 表示，代表編號 $u_i$ 的參賽者和編號 $v_i$ 的參賽者認識，且如果他們被分在同一隊的話，會對整個比賽貢獻 $c_i$ 的「內卷度」。
身為一個邪惡的出題者，你的目標是最大化整個比賽的內卷度總和，讓大家感受痛苦。現在，給定你所有的內卷關係以及 $Q$ 種選大隊長的方式，請你計算每一種選大隊長的方案下，分隊後最大的「內卷度總和」是多少？
Input Format
輸入第一行有三個正整數 $N$、$M$ 和 $Q$，意義如題所述。
接下來有 $M$ 行，第 $i$ 行有三個正整數 $u_i, v_i, c_i$，意義如題所述。
接下來有 $Q$ 行，每行有兩個正整數 $s_j$ 和 $t_j$，代表第 $j$ 種選大隊長的方案是任命 $s_j$ 和 $t_j$ 當內卷大隊長。
- 所有的輸入都是正整數
- $2 \le N \le 500$
- $1 \le M \le \min(\frac{N(N-1)}{2}, 1500)$
- $1 \le Q \le \min(\frac{N(N-1)}{2}, 10 ^ 5)$
- $\forall i \in [1, M], 1 \le u_i, v_i \le N, u_i \ne v_i$
- $\forall i, j \in [1, M], i \ne j \Rightarrow (v_j, u_j) \ne (u_i, v_i) \ne (u_j, v_j)$
- $\forall i \in [1, M], 1 \le c_i \le 2 ^ {30}$
- $\forall j \in [1, Q], 1 \le s_j, t_j \le N, s_j \ne t_j$
Output Format
對於每一種選內卷大隊長的方式，輸出一行包含一個整數，代表該種選大隊長的方案下，分隊後最大的內卷度總和是多少。
Sample Input 1
4 6 6
1 2 9
1 3 6
1 4 1
2 3 1
2 4 4
3 4 2
1 2
1 3
1 4
2 3
2 4
3 4
1 2 9
1 3 6
1 4 1
2 3 1
2 4 4
3 4 2
1 2
1 3
1 4
2 3
2 4
3 4
Sample Output 1
10
14
16
14
16
16
14
16
14
16
16
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資。 | 0 |
| 2 | 1~9 | $N \le 20, Q = 1$ | 10 |
| 3 | 1~39 | $Q = 1$。 | 70 |
| 4 | 0~69 | 無特別限制。 | 20 |