2444. sunny的花园

单点时限: 2.0 sec

内存限制: 256 MB

太阳 GG 有两座矩形花园 GA,GB,每个花园里有 N 个小亭子,亭子标号分别为 GA1.GA2…GAN,GB1.GB2…GBN. 他把两个花园都装修得一模一样,无论是长宽,还是园子里的亭子,甚至是亭子的位置,甚至是。也就是说 GA 花园里的 GAi 与 GB 花园里的 GBi (1<=i<=N) 是对应的。

一场暴雨过后,将 GA 花园里连接不同亭子之间的小路都破坏了,GG 的朋友小强帮他重新建造了小路,但是后来 GG 发现 GA 的小路和 GB 的小路是不一样的。作为一个没有方向感的人,他不愿意在自己的花园里迷路,而且只愿意记住一个花园的地图。所以他想修改两个花园的道路,使得他们小路的布局完全一样。小路指的是连接两个亭子的直接路径,不经过中间节点。

格局完全一样也就是说

如果 GA 有一条小路连接 GAi 和 GAj, 则 GB 里面也必须有一条小路连接 GBi 和 GBj(因为 GAi 对应 GBi,GAj 对应 GBj);

如果 GA 有没有小路连接 GAi 和 GAj, 则 GB 里面也不能有一条小路连接 GBi 和 GBj

对于每座花园,有两种修改操作

(1) 添加一条直接小路 (a,b), 添加的花费在 GA,GB 中分别为 IA,IB

(2) 删除一条直接小路 (a,b), 删除的花费在 GA,GB 中分别为 DA,DB

给出两个花园的道路布局修改,GG 让你帮忙进行一系列的添加或是删除操作,将两个花园道路布局改造得一样,同时改造的耗费最小

hint: 即使最后所有亭子都不连接在一起也无所谓 :)

输入格式

第一行有一个整数 T, 表示有 T 组测试数据

每组数据

第一行为 N(1<=N<=100)

第二行有四个以空格间隔的整数 IA,IB,DA,DB( 0<=IA,IB,DA,DB<=1000),接下来是个 N*N 的矩阵表示 GA 花园的道路布局,有 N 行,每行 N 个整数,a(ij) 表示第 i 行 j 列的数,a(ij)=0 表示 GAi 和 GAj 没有相连的小路

,a(ij)=1 表示 GAi 和 GAj 有相连的小路,当然 a(ii)=0;

同理接下来有一个 N*N 表示 GB 花园道路布局的矩阵

由于小路是无向的,所以 a(ij) 等于 a(ji), 道路矩阵为对称矩阵

输出格式

每组数据输出一个整 (一行),表示修改道路的最小花费。

样例

Input
3
3
6 3 9 7
0 1 0
1 0 1
0 1 0
0 1 1
1 0 1
1 1 0
3
8 4 17 9
0 0 0
0 0 1
0 1 0
0 0 1
0 0 1
1 1 0
4
18 15 3 8
0 0 1 0
0 0 0 1
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 0
Output
6
8
22

39 人解决,69 人已尝试。

45 份提交通过,共有 85 份提交。

4.5 EMB 奖励。

创建: 11 年,9 月前.

修改: 3 年前.

最后提交: 5 月前.

来源: 2008年选拔赛

题目标签