题意很简单，不叙述了，我分别用二分匹配和最大流实现了一下这道题，算是对前面所学知识的一次综合运用吧。
这是二分匹配：
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
int Map[200][200] ;
int link[200] ;
bool vis[200] ;
int n , m ,s, v;
int dfs(int now)
{
for (int i = 1 ;i <= m ;i ++)
{
if(Map[now][i])
if(!vis[i])
{
vis[i] = 1 ;
if(link[i] == -1 || dfs(link[i]))
{
link[i] = now ;
return 1 ;
}
}
}
return 0 ;
}
struct pp
{
double x, y;
}a[200],b[200] ;
bool Can(pp x ,pp y)
{
double dis = sqrt((x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y)) ;
double t = dis / v ;
if(t <= s)
return 1 ;
return 0;
}
void build()
{
REP(i,1,n)
{
REP(j,1,m)
{
Map[i][j] = Can(a[i],b[j]) ;
}
}
}
int main()
{
while(cin >> n >> m >> s >> v )
{
REP(i,1,n)cin >> a[i].x >> a[i].y ;
REP(i,1,m)cin >> b[i].x >> b[i].y ;
build() ;
mem(link ,-1) ;
int ans = 0 ;
REP(i,1,n)
{
mem(vis,0) ;
ans += dfs(i) ;
}
cout << n - ans <
return 0;
}
这是网络流：
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include