欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

SSL1333 地鼠的困境【二分图匹配】【匈牙利算法】

程序员文章站 2022-03-23 09:13:11
这道题其实也差不多是一个模板题注意有多组数据即可。代码#include#include#include#include#includeusing namespace std;int T,n,m,v,s,tot,ans,link[1010],vis[1010],ls[1010];double dzx[1010],dzy[1010],sdx....

SSL1333 地鼠的困境【二分图匹配】【匈牙利算法】
这道题其实也差不多是一个模板题
注意有多组数据即可。

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;

int T,n,m,v,s,tot,ans,link[1010],vis[1010],ls[1010];
double dzx[1010],dzy[1010],sdx,sdy;

struct node
{
	int y,next;
}map[1000010];
void add(int x,int y)
{
	map[++tot].y=y;
	map[tot].next=ls[x];
	ls[x]=tot;
}
int dfs(int x)
{
	for(int i=ls[x]; i; i=map[i].next)
	 {
	 	int y=map[i].y;
	 	if(!vis[y])
	 	 {
	 	 	vis[y]=1;
	 	 	int fa=link[y];
	 	 	link[y]=x;
	 	 	if(fa==0||dfs(fa))
	 	 	  return 1;
	 	 	link[y]=fa;
	 	 }
	 }
	return 0;
}
int main()
{
    cin>>T;
    while(T--)
     {
     	scanf("%d%d%d%d",&n,&m,&s,&v);
     	for(int i=1; i<=n; i++)
     	   scanf("%lf%lf",&dzx[i],&dzy[i]);
     	for(int i=1; i<=m; i++)
     	 {
     	   scanf("%lf%lf",&sdx,&sdy);
     	   for(int j=1; j<=n; j++)
     	    {
     	       double dis=sqrt((sdx-dzx[j])*(sdx-dzx[j])+(sdy-dzy[j])*(sdy-dzy[j]));
     	       if(dis<=s*1.0*v*1.0)  //能到达才建边
     	         add(j,i);
     	    }
     	 }
     	for(int i=1; i<=n; i++)
     	 {
     	 	memset(vis,0,sizeof(vis));
     	 	if(dfs(i))
     	 	  ans++;
     	 }
     	cout<<n-ans<<endl;   //受到攻击的,不是不受到攻击的 
     	memset(link,0,sizeof(link));  //数组,变量清零
     	memset(ls,0,sizeof(ls));
     	tot=0,ans=0;
     }
    return 0;
}

本文地址:https://blog.csdn.net/Jackma_mayichao/article/details/108163395