Gopher（二分图最大匹配）

￡神魔★判官ぃ 2022-08-01 03:16 210阅读 0赞

## Problem K: Gopher ##

Time Limit: 1 Sec   Memory Limit: 128 MB  
Submit: 5   Solved: 4  
\[ [Submit][]\]\[ [Status][]\]\[ [Web Board][]\]

## Description ##

The gopher family, having averted the canine threat, must face a new predator.

The are *n* gophers and *m* gopher holes, each at distinct (x, y) coordinates. A hawk arrives and if a gopher does not reach a hole in *s* seconds it is vulnerable to being eaten. A hole can save at most one gopher. All the gophers run at the same velocity *v*. The gopher family needs an escape strategy that minimizes the number of vulnerable gophers.

## Input ##

The input contains several cases. The first line of each case contains four positive integers less than 100: *n*, *m*, *s*, and *v*. The next *n* lines give the coordinates of the gophers; the following *m* lines give the coordinates of the gopher holes. All distances are in metres; all times are in seconds; all velocities are in metres per second.

## Output ##

Output consists of a single line for each case, giving the number of vulnerable gophers.

## Sample Input ##

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

## Sample Output ##

## HINT ##

这个是二分图匹配！

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<iostream>
    using namespace std;
    int n,m;
    int map[500][500];
    int isv[500];
    int h[500];
    struct p
    {
        double x;
        double y;
    }a[500],b[500];
    int success(int x)
    {
        int i;
        for(i=1;i<=m;i++)
        {
            if(!isv[i]&&map[x][i]==1)
            {
                isv[i]=1;
                if(!h[i]||success(h[i]))
                {
                    h[i]=x;
                    return 1;
                }
            }
        }
        return 0;
    }
    int main()
    {
        int t,v,i,j,num;
        double area;
        while(cin>>n>>m>>t>>v)
        {
            num=0;
            memset(map,0,sizeof(map));
            memset(h,0,sizeof(h));
            for(i=1;i<=n;i++)
            {
                cin>>a[i].x>>a[i].y;
            }
            for(i=1;i<=m;i++)
            {
                cin>>b[i].x>>b[i].y;
            }
            for(i=1;i<=n;i++)
            {
                for(j=1;j<=m;j++)
                {
                    area=sqrt((a[i].x-b[j].x)*(a[i].x-b[j].x)+(a[i].y-b[j].y)*(a[i].y-b[j].y));
                    if(area<=1.0*t*v)
                    {
                        map[i][j]=1;
                    }
                }
            }
            for(i=1;i<=n;i++)
            {
                memset(isv,0,sizeof(isv));
                if(success(i))
                {
                    num++;
                }
            }
            cout<<n-num<<endl;
        }
    }

[Submit]: http://cst2.jlnu.edu.cn/acm/submitpage.php?cid=1007&pid=10&langmask=32756
[Status]: http://cst2.jlnu.edu.cn/acm/problemstatus.php?id=1406
[Web Board]: http://cst2.jlnu.edu.cn/acm/bbs.php?pid=1406&cid=1007