sicily1684 Christmas
IAmL
posted @ 2009年4月11日 07:32
in 解题报告
with tags
sicily1684 Christmas解题题报告
, 2280 阅读
题意：有n pairs男女参加party，然后每个人身高和年龄不同，所以男女组合的时候难免有不爽。然而不知道为什么，不爽程度居然可以算出来：F(i,j)=(Hi-Hj)^2+(AGEi-AGEj)^2 。然后要求最大不爽程度的最小值。<-(类似poj的frogger)
本题开始时毫无头绪，不过之后看了argo的讨论之后，发现解似曾相似。这题用的是二分+匹配。匹配当然可以理解，但是要用二分又是为什么呢？原来我们要求的是众多匹配方案中，最大的最小不爽值。所以理所当然地想到要枚举所有的匹配方案，然后最终找出符合条件的边。这样固然是可以理解的，但是会超时。所以这里引入搜索技术。通过举出边的上界，来不断逼近目标解。这样就有一个问题：是不是一定能用二分法求出边？即有没有可能求出的边的值不在给出的边集里面呢？答案是不可能。因为考虑一下可以发现，如果我们找到的边值如果不是最优解（即不在给出的边集里面的话，我们可以找到另外的边使得符合条件而且在边集里面）。这个枚举可行解的界从而不断逼近可行解的技术，过去曾经听说过，叫参数搜索。这里又再次遇到，就写下了这篇日志，以作备忘。
另外，再次膜拜一下用此方法做出此题的大牛们～ OTZ
＝＝＝＝＝＝＝＝＝＝＝＝来路不明的分割线＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
注：代码中要注意的是二分搜索的写法，因为写得不好会进入死循环。
#include <iostream>
using namespace std;
#define Max 12500
#define N 501
int linked[N], f[N][N], man[N][2], woman[N][2], n, mid;
bool used[N];
bool can(int t)
{
int i;
for (i = 0; i < n; i++)
{
if (!used[i] && f[t][i] < mid)
{
used[i] = true;
if (linked[i] == -1 || can(linked[i]))
{
linked[i] = t;
return true;
}
}
}
return false;
}
int match()
{
int i, m = 0;
memset(linked, -1, sizeof(linked));
for (i = 0; i < n; i++)
{
memset(used, false, sizeof(used));
if (can(i)) m++;
}
return m;
}
int main()
{
int i, j, tmp1, tmp2, low, high, m;
while (cin >> n, n)
{
memset(f, 0, sizeof(f));
for (i = 0; i < n; i++) cin >> man[i][0] >> man[i][1];
for (i = 0; i < n; i++) cin >> woman[i][0] >> woman[i][1];
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
//F(i,j)=(Hi-Hj)^2+(AGEi-AGEj)^2
tmp1 = man[i][0] - woman[j][0];
tmp2 = man[i][1] - woman[j][1];
tmp1 *= tmp1;
tmp2 *= tmp2;
f[i][j] = tmp1 + tmp2;
//test
// cout << f[i][j] <<" ";
}
//test
// cout << endl;
}
low = 0;
high = Max;
while (low < high)
{
mid = (low + high) / 2;
m = match();
if (m >= n) high = mid;
else low = mid + 1;
}
cout << low - 1 << endl;
}
return 0;
}
using namespace std;
#define Max 12500
#define N 501
int linked[N], f[N][N], man[N][2], woman[N][2], n, mid;
bool used[N];
bool can(int t)
{
int i;
for (i = 0; i < n; i++)
{
if (!used[i] && f[t][i] < mid)
{
used[i] = true;
if (linked[i] == -1 || can(linked[i]))
{
linked[i] = t;
return true;
}
}
}
return false;
}
int match()
{
int i, m = 0;
memset(linked, -1, sizeof(linked));
for (i = 0; i < n; i++)
{
memset(used, false, sizeof(used));
if (can(i)) m++;
}
return m;
}
int main()
{
int i, j, tmp1, tmp2, low, high, m;
while (cin >> n, n)
{
memset(f, 0, sizeof(f));
for (i = 0; i < n; i++) cin >> man[i][0] >> man[i][1];
for (i = 0; i < n; i++) cin >> woman[i][0] >> woman[i][1];
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
//F(i,j)=(Hi-Hj)^2+(AGEi-AGEj)^2
tmp1 = man[i][0] - woman[j][0];
tmp2 = man[i][1] - woman[j][1];
tmp1 *= tmp1;
tmp2 *= tmp2;
f[i][j] = tmp1 + tmp2;
//test
// cout << f[i][j] <<" ";
}
//test
// cout << endl;
}
low = 0;
high = Max;
while (low < high)
{
mid = (low + high) / 2;
m = match();
if (m >= n) high = mid;
else low = mid + 1;
}
cout << low - 1 << endl;
}
return 0;
}
评论 (0)