在一個國家中,會有許許多多的企業,
每個企業都會各司其職,負責不同的事務,
而且有些企業因為產業鏈相近的關係,
如果在同一個廠區的話會有經濟效益上的加成。
但是現在因為政府的施政規劃,
所以想將這些企業分配到兩個廠區,
但又希望可以找到一個方法,
使得在分完後的總經濟效益最高,
也就是要求出一個總經濟效益最高的分配方式,
並計算其獲得之總經濟效益為多少。
而總經濟效益的計算方式如下:
令 $Con(a,b)=r$ 表示當 $a$ 與 $b$ 在同一廠區時,貢獻 $r$ 單位的經濟效益;
假設:
則最好的策略是將 $A,B,C$ 分配在同一個廠區,$D,E$ 在另一個廠區,
這樣獲得的總經濟效益為第一個廠區的 $Con(A,B)+Con(A,C)+Con(B,C)$,
加上第二個廠區的 $Con(D,E)$,
總合為 $(4+5+3)+(6)=18$。
但是某些企業因為一些因素,必須要在指定廠區才能作業。
使用上面的例子,假設 $A$ 必須在第一廠區,
$B$ 必須在第二廠區,
則最佳解為 $A,C$ 在第一廠區,其餘的在第二廠區。
總經濟效益為 $15$。
保證兩個廠區都至少會有一間企業必須在該廠區作業。
第一行輸入兩個整數 $N,M$,代表企業數量與經濟效益關係數量。
接下來一行,第一個數字 $K_A$ 代表必須在第一個廠區作業的企業數量,接著會有 $K_A$ 個數字 $A_i$ 代表那些企業的編號。
接下來一行,第一個數字 $K_B$ 代表必須在第二個廠區作業的企業數量,接著會有 $K_B$ 個數字 $B_j$ 代表那些企業的編號。
接下來 $M$ 行,每行有三個數字 $a_k,b_k,r_k$,代表 $Con(a_k,b_k)=r_k$。
請輸出一個數字,代表在最好的分配方法下,最多可以獲得多少的總經濟效益。
No. | Testdata Range | Score |
---|---|---|
1 | 0~22 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 1000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 1000 | 65536 | 65536 | |
9 | 1000 | 65536 | 65536 | |
10 | 1000 | 65536 | 65536 | |
11 | 1000 | 65536 | 65536 | |
12 | 1000 | 65536 | 65536 | |
13 | 1000 | 65536 | 65536 | |
14 | 1000 | 65536 | 65536 | |
15 | 1000 | 65536 | 65536 | |
16 | 1000 | 65536 | 65536 | |
17 | 1000 | 65536 | 65536 | |
18 | 1000 | 65536 | 65536 | |
19 | 1000 | 65536 | 65536 | |
20 | 1000 | 65536 | 65536 | |
21 | 1000 | 65536 | 65536 | |
22 | 1000 | 65536 | 65536 |