二分图最大匹配-POJ 2536/UVA 10080-Gopher II

落日映苍穹つ 2022-05-16 08:08 114阅读 0赞

*  # 二分图最大匹配-POJ 2536/UVA 10080-Gopher II #

--------------------

*  ## 题目链接： ##

### **POJ：[Gopher II][]** ###

### **UVA：[10080 - Gopher II][]** ###

*  ## 思路： ##

**题目大意是有n只地鼠，m个鼠洞（一个洞只能容纳一只地鼠），地鼠跑的速度为v，过了s秒还没进洞的地鼠会被捉，问最大地鼠存活的数量。**

**找出每只鼠在规定时间s内能到达的洞，也就是尽可能安排多的地鼠进洞，二分图最大匹配的题目**

用匈牙利算法实现

*  ## 基础： ##

### **[匈牙利算法（Hungarian）][Hungarian]** ###

*  ## 代码： ##

#include<iostream>
    #include<cmath>
    #include<memory.h>
    using namespace std;
    #define MAX_SIZE 123
    struct Point
    {
        double x;
        double y;
    };
    Point Gopher[MAX_SIZE];  //地鼠位置
    Point Holes[MAX_SIZE];   //鼠洞位置
    bool Line[MAX_SIZE][MAX_SIZE]={0};  
    bool Visit[MAX_SIZE];
    int To_Holes[MAX_SIZE]={0};  //安排结果
    int n,m;
    double s,v;
    
    bool Match(int Index)
    {
        for(int i=1;i<=m;i++)
        {
            if(Line[Index][i]==true&&Visit[i]==false)  //该鼠可能跑进该洞并且调剂时该洞没被预占
            {
                Visit[i]=true;   //标记该洞暂时有鼠
                if(To_Holes[i]==0||Match(To_Holes[i])) //该洞没鼠或者可以腾出该洞
                {
                    To_Holes[i]=Index;
                    return true;
                }
            }
        }
        return false;
    }
    
    int Hungarian()
    {
        int Cnt=0;
        for(int i=1;i<=n;i++)
        {
            memset(Visit,0,sizeof(Visit));
            if(Match(i))
                Cnt++;
        }
        return n-Cnt;
    }
    
    int main()
    {
        while(cin>>n>>m>>s>>v)
        {
            memset(To_Holes,0,sizeof(To_Holes));
            for(int i=1;i<=n;i++)
                cin>>Gopher[i].x>>Gopher[i].y;
            for(int i=1;i<=m;i++)
            {
                cin>>Holes[i].x>>Holes[i].y;
                for(int j=1;j<=n;j++)
                {
                    double Dis=sqrt(pow(Holes[i].x-Gopher[j].x,2)+pow(Holes[i].y-Gopher[j].y,2));
                    if(Dis>v*s)
                        Line[j][i]=false;   //找出每只鼠可以成功逃生的洞并标记
                    else
                        Line[j][i]=true;
                }
            }
            int Res=Hungarian();
            cout<<Res<<endl;
        }
        return 0;
    }

[Gopher II]: http://poj.org/problem?id=2536
[10080 - Gopher II]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1021
[Hungarian]: https://blog.csdn.net/SZU_Crayon/article/details/81784389