【openjudge 1538】Gopher II（匈牙利算法）

本文主要是介绍【openjudge 1538】Gopher II（匈牙利算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[题意][田野上有一群老鼠和一些老鹰，老鹰捉老鼠，田野上同时存在一些地洞，老鼠躲到地洞里老鹰就捉不到。给你老鼠的个数n、地洞的个数m、老鼠的奔跑速度v、最大限时间s（即不能再规定时间内不能到达地洞，就会被老鹰吃掉），老鼠和地洞的坐标。看至少有几只老鼠被吃。]

[本质：求二分图的最大匹配]

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
double a1[110][2],a2[110][2];
int m,n,s,v,d[110][110],ans,dis[110];
bool p[110];
double do1(double x1,double y1,double x2,double y2)
{double x,y,z;x=fabs(x1-x2); y=fabs(y1-y2);//实数的绝对值fabs,刚开始我用成了abs，结果WA了 x*=x; y*=y;z=sqrt(x+y);return z;
}
bool dfs(int s)
{int j;for (j=1;j<=m;j++)if (d[s][j]&&p[j]==false){p[j]=true;if (dis[j]==-1||dfs(dis[j])){dis[j]=s;return true;}}return false;
}
int main()
{int i,j;while (scanf("%d%d%d%d",&n,&m,&s,&v)==4){ans=0;memset(a1,0,sizeof(a1));memset(a2,0,sizeof(a2));memset(d,0,sizeof(d));for (i=1;i<=n;i++)scanf("%lf%lf",&a1[i][0],&a1[i][1]);for (i=1;i<=m;i++)scanf("%lf%lf",&a2[i][0],&a2[i][1]);for (i=1;i<=n;i++)for (j=1;j<=m;j++)if (do1(a1[i][0],a1[i][1],a2[j][0],a2[j][1])<=s*v)d[i][j]=1;memset(dis,-1,sizeof(dis));for (i=1;i<=n;i++){memset(p,false,sizeof(p));if (dfs(i))  ans++;}printf("%d\n",n-ans);}return 0; 
}

这篇关于【openjudge 1538】Gopher II（匈牙利算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---