E |
Component
Placement Input: Standard Input Output: Standard Output |
In circuit
design, component placement is an important step in the design automation.
Inferior placements may affect the performance and manufacturing cost.
You are given a PCB (Printed
Circuit Board). It's a large green board. You can place components on either
side of the PCB. However, cost of placing a component on both sides are not the
same. You are given N
components. For each component ci,
cost of placing it on the top layer is Xi and on the bottom layer is Yi.
These components may interact
with each other. If both the components are on the same side of the PCB, the
interconnection cost is negligible. But, if they are on different sides, their
interconnection is costly. For each such interconnection j, the cost will be Zj.
Finally, some design issues restricts
some components to be on the top side or bottom side. Now, find the minimum
cost to place the components.
First line contains a positive
integer T (T<= 50)
that denotes the number of test cases.
Each test case starts with 2
integers N (1 <= N <= 200)
and M (0 <= M <= 100000, M <= N * (N-1) / 2), the
number of components and number of interconnections. This will be followed by N
integers in a line, each between 1 and 10000000 (inclusive), where i-th
of it describes the cost of placing the component on the top layer. The next
line contains N more
integers, each between 1 and 10000000 (inclusive), where i-th of it denotes
the cost of placing it on the bottom layer. The next line contains N more integers, each will be
either 0, -1 or +1, where
·
-1 means i-th component can only be placed
on the bottom
·
+1 means i-th component can only be placed
on the top
·
0 means the component can be placed on either side
Then there will be M lines,
each containing three integers, p,
q, and r (1 <= p, q <= N, 1 <= r <=
10000000), denoting that, p
and q-th component has
to be interconnected and if they are on different layers, the cost of
interconnection will be r.
There will be at most one interconnection between any pair or components.
For each test case, output the minimum cost to place the
components.
5 4
0 5
6 7 8 8
7 6 5 0
0 0 0 4
2 5
6 7 8 8
7 6 5 0
0 0 0 1
3 10 2
4 10 4
3 5
6 7 8 8
7 6 5 0
0 0 0 1
3 10 2
4 10 2
3 1 4
3 5
6 7 8 30
31 32 33 0
0 0 0 1
3 10 2
4 10 2
3 1 4
3 5
6 7 8 8
7 6 5 -1
0 0 1 1
2 10 3
4 10 2
3 1 |
22 24 25 26 31 |
Problemsetter: Manzurur Rahman Khan
Special Thanks: Samee Zahur