#2283. 画框

    ID: 2283 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>PROV赛事:contest2459来源:qoj.ac数据:公开样例网络流

画框

画框

题目描述

2014‐05‐10  第2 页,共7 页  第1 题:画框(frame),运行时限2s,内存上限128M,100 分。 【问题描述】 小T 准备在家里摆放几幅画,为此他买来了N 幅画和N 个画框。为了体现他的品味,小 T 希望能合理地搭配画与画框,使得其显得既不过于平庸也不太违和。对于第i 幅画与第j 个 画框的配对,小T 都给出了这个配对的平凡度Ai,j 与违和度Bi,j。整个搭配方案的总体不和谐 度为每对画与画框平凡度之和与每对画与画框违和度之和的乘积。具体来说,设搭配方案中第 i 幅画与第Pi 个画框配对,则总体不和谐度为 , , 1 1 * i i N N i P i P i i disharmony A B    

小T 希望知道通过搭配能得到的最小的总体不和谐度是多少。 【输入格式】 输入文件名为frame.in。 输入文件第1行是一个正整数T,表示数据组数。 接下来是T组数据。 对于每组数据: 第1行是一个正整数N,表示有N对画和画框; 第2到第N+1行,每行有N个非负整数,第i+1行第j个数表示Ai,j;
第N+2到第2N+1行,每行有N个非负整数,第i+N+1行第j个数表示Bi,j。 【输出格式】 输出文件名为frame.out。 输出文件仅包含T 行,每行一个整数,表示最小的总体不和谐度。 【输入输出样例】 frame.in frame.out 1 3 4 3 2 2 3 4 3 2 1 2 3 2 2 2 4 1 1 3 30 【样例解释】 第1幅画搭配第3个画框,第2幅画搭配第1个画框,第3幅画搭配第2个画框,则总体不和谐 度为(2+2+2)*(2+2+1)=30。 【数据范围】 对于10%的数据满足N≤10,T≤2; 对于30%的数据满足Ai,j=Bi,j;

2014‐05‐10  对于70%的数据满足N≤40; 对于100%的数据满足N≤70,T≤3,Ai,j≤200,Bi,j≤200。 【编译命令】

对于c++语言: g++ -o frame frame.cpp –lm 对于c语言: gcc -o frame frame.c –lm 对于pascal语言: fpc frame.pas

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

1
3
4 3 2
2 3 4
3 2 1
2 3 2
2 2 4
1 1 3
30