UVA 10080 - Gopher II

UVA 10080 - Gopher II

題目概述:

二分圖最大匹配 裸題。

思路:

建模的方式為將每隻老鼠可達到的老鼠洞連邊。(以下code實作方式為將hole連向mouse)

//By SCJ

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

int n,m,s,v;

struct P{

   double x,y;

};

P hole[102],mou[102];

vector<int> G[102];//hole->mou

bool used[102];

int match[102];

bool dfs(int u)

{

   for(int v:G[u])

   {

       if(!used[v])

       {

           used[v]=1;

           if(match[v]==-1||dfs(match[v]))

           {

               match[v]=u;

               return true;

           }

       }

   }

   return false;

}

int solve()

{

   memset(match,-1,sizeof(match));

   int res=0;

   for(int i=1;i<=m;++i)

   {

       memset(used,0,sizeof(used));

       if(dfs(i)) res++;

   }

   return res;

}

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   while(cin>>n>>m>>s>>v)

   {

       for(int i=1;i<=n;++i) cin>>mou[i].x>>mou[i].y;

       for(int i=1;i<=m;++i) cin>>hole[i].x>>hole[i].y;

       for(int i=1;i<=m;++i)

       {

           for(int j=1;j<=n;++j)

           {

               P a=hole[i],b=mou[j];

               double d=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

               if( d/v <= s )  G[i].push_back(j);

           }

       }

       cout<<n-solve()<<endl;

       for(int i=0;i<=n;++i) G[i].clear();

   }

}