题意:有n个晏鼠 m个洞,给出他们的坐标,每个晏鼠的速度都是一样的V
如果在s秒内,它们没有跑到洞是就会被老鹰吃掉,每个洞只能容纳一个晏鼠 求最后有多少晏鼠会被吃掉
思路: 这是个比较简单的二分图最大匹配问题,建图也相对简单,只在晏鼠到洞的距离小于V*S 就把他们连起来 求出最大匹配
再用n-最大匹配
#include <stdio.h>
#include <string.h>
#include <math.h>
#define M 110
int n,m;
int map[M][M],link[M],vis[M];
struct node
{
double
x,y;
}g[M],h[M];
double len (node a,node b)
{
......
阅读全文