POJ 2536 Gopher II（二分圖的最大匹配）

POJ 2536 Gopher II（二分圖的最大匹配）

題意：已知有n只老鼠的坐標，m個洞的坐標，老鼠的移動速度為V,S秒以後有一只老鷹要吃老鼠，問有多少個老鼠被吃。

很明晰，二分匹配，老鼠為X集合，洞為Y集合

#include 
#include 
#include 
#include 
#include 
#include 
#define init(a) memset(a,0,sizeof(a))
#define PI acos(-1,0)
using namespace std;
const int maxn = 310;
const int maxm = 100001;
#define lson left, m, id<<1
#define rson m+1, right, id<<1|1
#define min(a,b) (a>b)?b:a
#define max(a,b) (a>b)?a:b
#include 
#include 
#include 
#include 
using namespace std;
int n,m,s,v,ma[500][500];
bool vis[500];
int line[500];
struct node
{
  double x,y;
};
node g[300],h[300];

int DFS(int u)
{
  for(int v = 1;v<=m;v++)
    {
    if(!vis[v]&&ma[u][v])
    {
      vis[v]=1;
      if(line[v]==-1 || DFS(line[v]))
    {
        line[v] = u;
        return 1;
      }
    }
  }
  return 0;
}
int K_M()
{
    memset(line,-1,sizeof(line));
    int ans=0;
    for(int i = 1;i<=n;i++)
    {
      init(vis);
      ans += DFS(i);
    }
    return ans;
}
int main()
{
  while(scanf(%d%d%d%d,&n,&m,&s,&v)!=EOF)
    {
    init(ma);
    for(int i=1;i<=n;i++)
    {
      scanf(%lf%lf,&g[i].x,&g[i].y);
    }
    for(int i=1;i<=m;i++)
    {
      scanf(%lf%lf,&h[i].x,&h[i].y);
    }
    for(int i=1;i<=n;i++)
    {
      for(int j=1;j<=m;j++)
        {
  double dis = sqrt((h[j].x-g[i].x)*(h[j].x-g[i].x)+(h[j].y-g[i].y)*(h[j].y-g[i].y));//老鼠與洞的距離

        if(dis / v <= (double)s)//老鼠到達洞的時間