TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  训练指南  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2798
  • 题目
  • P2798【CH "清明欢乐赛"】男女搭配
    限制 : 时间限制 : 5000 MS   空间限制 : 165536 KB
    评测说明 : 每组0.5s
    问题描述

    背景
    有n个汉子的和n个妹子,每个人都有自己喜欢的唯一的异性,现在他们要开始考虑一些事情了。

    描述
    每个人都要和一名异性在一起(不能多不能少),但这往往会产生冲突,因为一个人喜欢的人可能并不能和他在一起。所以在这个过程中会产生一些不愉悦。每个人如果没有和自己喜欢的异性在一起,会产生一定的不愉悦值。求一个最好的搭配,使得不愉悦值最小。

    输入格式

    输入有5行,第一行有一个正整数n
    第二行有n个正整数,依次表示各个汉子心目中的妹子
    第三行有n个正整数,依次表示各个妹子心目中的汉子
    第四行有n个正整数,依次表示每个汉子没和喜欢的人在一起产生的不愉悦值
    第五行有n个正整数,依次表示每个妹子没和喜欢的人在一起产生的不愉悦值

    输出格式

    输出只有一个最小不愉悦值。

    样例输入

    2
    1 1
    2 2
    2 1
    1 2

    样例输出

    2

    提示

    样例解释:
    尽管第2个汉子和第一个妹子互相喜欢,但他们如果在一起,总不愉悦值为4;
    如果满足第一个汉子和第二个妹子的要求,总不愉悦值为2,最优。

    数据范围与约定:
    20%的数据,0<n<=10。
    60%的数据,0<n<=100。
    80%的数据,0<每个人的不愉悦值<=100。
    100%的数据,0<n<=1000,0<每个人的不愉悦值<=100000。


    来源  来自Contest Hunter,由lll6924命题,感谢nodgd搬运工