【ssl1333】地鼠的困境【最大匹配】【匈牙利算法】

Description

地鼠家族面临着一个新的威胁——猎食者。
　　地鼠家族一共有N个地鼠和M个鼠洞，每个都位于不同的(x, y)坐标中。假如有地鼠在发觉危险以后s秒内都没有回到鼠洞里的话，就可能成为老鹰的食物。当然了，一个鼠洞只能拯救一只地鼠的命运，所有地鼠都以相等的速度v移动。地鼠家族需要设计一种策略，使得老鹰来时，易受攻击的地鼠数量最少。

Input

本题有多组数据。第1行为测试数据组数T(T<=50)。
对于每组数据，第一行4个整数n, m, s和v(n, m <= 100)。以后n行为地鼠的坐标，以后m行为鼠洞的坐标。距离的单位是m，时间的单位是s，速度的单位是m/s。

Output

对于每组数据输出一行，为易受攻击的地鼠的数量。

Sample Input

1
2 2 5 10
1.0 1.0
2.0 2.0
100.0 100.0
20.0 20.0

Sample Output

1

分析

先枚举所有的鼠洞和地鼠，算出距离，然后判断地鼠是否可以在规定时间内跑回鼠洞，可以的话就连边。
然后跑匈牙利算法（就是模板），求出最大匹配，然后用总的点数减去最大匹配，就是题目要求的答案。

注意有多组数据，记得数组清零。

上代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<cmath>
typedef long long ll;
using namespace std;

int t,n,m,s,v,link[100001],cover[100001],hd[100001],tot,ans;
double x[100001],y[100001],x1,y2;

struct node
{
	int to,next;
}a[100001];

void add(int l,int r)
{
	a[++tot]=(node){r,hd[l]};
	hd[l]=tot;
}

bool find(int k)
{
	for(int i=hd[k];i>0;i=a[i].next)
	{
		int j=a[i].to;
		if(cover[j]==0)
		{
			cover[j]=1;
			int q=link[j];
			link[j]=k;
			if(q==0||find(q))
			{
				return true;
			}
			link[j]=q;
		}
	}
	return false;
}

int main()
{
    cin>>t;
    while(t--)
    {
    	cin>>n>>m>>s>>v;
    	for(int i=1;i<=n;i++)
    	{
    		cin>>x[i]>>y[i];
    	}
    	for(int i=1;i<=m;i++)
        {
        	cin>>x1>>y2;
        	for(int j=1;j<=n;j++)
        	{
        		double dis=sqrt((x1-x[j])*(x1-x[j])+(y2-y[j])*(y2-y[j]));
        		if(dis<=s*v)
        		{
        			add(j,i);//用点连边而不是坐标 
        		}
        	}
        }
        for(int i=1;i<=n;i++)
		{
			memset(cover,0,sizeof(cover));
			find(i);
		} 
		for(int i=1;i<=n;i++)
		{
			if(link[i]!=0)
			{
			    ans++;
			}
		}
		cout<<n-ans<<endl;
		memset(link,0,sizeof(link));
		memset(hd,0,sizeof(hd));
		tot=0;
		ans=0; 
    }
	return 0;
}

本文地址：https://blog.csdn.net/dglyr/article/details/108168086