「JoyOI1982」武器分配

2014年2月25日3,0630

描述 Description

后勤部队运来一批武器(机枪和盔甲)。你要把这些武器分配给手下的marine们(每人一部机枪,一套盔甲)。可是问题来了。。。
这些武器的型号不相同(武器是由出价最低的承包商制造的),把一部m型的机枪和一套n型的盔甲分配给一个marine得到的不满意值为(m-n)^2(每个marine当然希望自己得到的武器是同一型号的)。
你的任务就是把a部机枪和b套盔甲分配给手下n个marine。使他们的不满意值之和最小。

输入格式 InputFormat

第一行:3 个正整数 n , a , b (1<=n<=a,b<=80)
第二行:a 个数表示每部机枪的型号
第三行:b 个数表示每套盔甲的型号
0<=型号值<=10000

输出格式 OutputFormat

输出一个数:最小不满意值。

样例输入 SampleInput

样例输出 SampleOutput

题解

费用流,裸题

每人一个机枪一个防弹衣,就像是一个二分图最大匹配,所以直接在所有机枪和所有防弹衣之间连上有向边,边的费用为(a[i]-b[j])^2,容量为1。

再加上超级源和超级汇,费用为0,容量为1。

最后再加一个第二汇点,超级汇和第二汇点相连,费用为0,容量为n,进行人数限制。

最后来一次最小费用最大流就可以了。

avatar
  Subscribe  
提醒