题目链接：
http://bjutacm.openjudge.cn/lianxi/1101/
思路：
二分 + 二分图最大匹配。
开始的时候我想直接用最小费用流模型，后来发现这样是错误的。因为这道题实际上是求一个匹配数>=n的匹配，并且满足在这个匹配中匹配边的最大的权值最小；而不是使所有匹配边的权值之和最小。这样看来就是一个典型的二分思路。首先对权值排序，每次选中原图中那些权值不能超过x的边，用这些边构建二分图。再用匈牙利算法check一下这个二分图的最大匹配数是否>=n。二分一下满足这样的条件下对应的最小的那个边权值x即可。
实现：
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std; const int MAXN = ;
int n, m;
double v, dis[MAXN + ][MAXN + ], edges[MAXN * MAXN + ];
vector<int> G[MAXN + ];
bool used[MAXN + ];
int match[MAXN + ]; struct point
{
int x, y;
};
point man[MAXN / + ], car[MAXN / + ]; bool dfs(int v)
{
used[v] = true;
for (int i = ; i < G[v].size(); i++)
{
int u = G[v][i];
int w = match[u];
if (w == - || !used[w] && dfs(w))
{
match[v] = u;
match[u] = v;
return true;
}
}
return false;
} int max_match()
{
int res = ;
for (int i = ; i <= n + m; i++)
{
if (match[i] == -)
{
memset(used, , sizeof(used));
if (dfs(i))
res++;
}
}
return res;
} bool check(double len)
{
for (int i = ; i <= n + m; i++)
match[i] = -;
memset(used, , sizeof(used));
for (int i = ; i <= n + m; i++)
G[i].clear();
for (int i = ; i < n; i++)
{
for (int j = ; j < m; j++)
{
if (dis[i][j] <= len)
{
G[i + ].push_back(j + n + );
G[j + n + ].push_back(i + );
}
}
}
return max_match() >= n;
} int square(int x)
{
return x * x;
} double cal_cost(int i, int j)
{
return sqrt(square(man[i].x - car[j].x) + square(man[i].y - car[j].y));
} int main()
{
while (cin >> n >> m)
{
for (int i = ; i < n; i++)
{
cin >> man[i].x >> man[i].y;
}
for (int i = ; i < m; i++)
{
cin >> car[i].x >> car[i].y;
}
cin >> v;
int cnt = ;
for (int i = ; i < n; i++)
{
for (int j = ; j < m; j++)
{
edges[cnt++] = dis[i][j] = cal_cost(i, j);
}
}
sort(edges, edges + cnt);
int l = , r = cnt - , res = cnt - ;
while (l <= r)
{
int mid = l + r >> ;
if (check(edges[mid]))
{
res = mid;
r = mid - ;
}
else
{
l = mid + ;
}
}
printf("%.2lf\n", edges[res] / v);
}
return ;
}