| 题目名称 | 566. 圣诞节 |
|---|---|
| 输入输出 | christmas.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 6 |
| 题目来源 |
 cqw
于2011-07-22加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：21， 提交：71， 通过率：29.58% | ||||
 _Itachi |
100 | 0.031 s | 0.38 MiB | C++ |
 APWTMECRD |
100 | 0.073 s | 0.37 MiB | C++ |
 烟雨 |
100 | 0.082 s | 0.37 MiB | C++ |
 可以的. |
100 | 0.106 s | 13.01 MiB | C++ |
 1 |
100 | 0.131 s | 0.00 MiB | C++ |
 老虎小飞 |
100 | 0.167 s | 5.11 MiB | Pascal |
 馒头 |
100 | 0.180 s | 5.91 MiB | C++ |
 王者自由 |
100 | 0.208 s | 0.38 MiB | C++ |
 cqw |
100 | 0.226 s | 16.77 MiB | C++ |
 @@@ |
100 | 0.251 s | 1.30 MiB | C++ |
| 本题关联比赛 | |||
| 20110723 | |||
| 20120418x | |||
| 20130418s | |||
| 关于 圣诞节 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
刚开始还以为要排序，结果发现匈牙利裸奔再外加一个二分就好了哈
| ||||
|
这是平方还是异或2.。。。。。
。。应该是平方。。。。 | ||||
|
我没二分为什么还比你们的快- -
网络流随便搞，匈牙利能搞的网络流都能搞  kaaala
2012-04-19 13:27
3楼
| ||||
|
实在想不到什么高端算法了就直接搜了
to Trojan: 额，这就是匈牙利？我一直不知道的说～ | ||||
|
膜拜KF ！！！那麼快～
======================= to KF: 你的代碼......不是hungary算法嗎？ 不知道怎麼優化的，巨快。 ========================== to kaaala: 求教網絡流算法。。 | ||||
瑆の時間~無盡輪迴·林蔭
HeHe
Makazeu【问题描述】
圣诞节要来了,有一个舞会.N个男士和N个女士将要参加.一个男士和一个女士成为一对舞伴.我们知道,如果一对舞伴的年龄和身高相差太多的话会不够和协.现在我们定义一个男士和一个女士的不和协值如下:
F(i,j)=(Hi-Hj)^2+(AGEi-AGEj)^2
Hi是i号人员的身高,AGEi是i号人员的年龄.你的任务是设计一个舞伴搭配方案,使最大不合协值最小.
【输入格式】
输入数据第一行为一个正整数N（N≤500），接下来有2N行；
每行包含两个正整数x,y，表示身高和年龄（100 ≤x≤200,10≤y≤60）,前N个表示男士,后N个表示女士。
【输出格式】
输出只有一个整数,表示最小的最大不和协值。
【样例输入】
2 141 27 134 10 169 34 178 18
【样例输出】
1801