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

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

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

  • 题目链接：

POJ：Gopher II

UVA：10080 - Gopher II

  • 思路：

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

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

用匈牙利算法实现

  • 基础：

匈牙利算法（Hungarian）

  • 代码：

    include

    include

    include

    using namespace std;

    define MAX_SIZE 123

    struct Point
    {

    1. double x;
    2. 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)
    {

    1. for(int i=1;i<=m;i++)
    2. {
    3.     if(Line[Index][i]==true&&Visit[i]==false)  //该鼠可能跑进该洞并且调剂时该洞没被预占
    4.     {
    5.         Visit[i]=true;   //标记该洞暂时有鼠
    6.         if(To_Holes[i]==0||Match(To_Holes[i])) //该洞没鼠或者可以腾出该洞
    7.         {
    8.             To_Holes[i]=Index;
    9.             return true;
    10.         }
    11.     }
    12. }
    13. return false;

    }

    int Hungarian()
    {

    1. int Cnt=0;
    2. for(int i=1;i<=n;i++)
    3. {
    4.     memset(Visit,0,sizeof(Visit));
    5.     if(Match(i))
    6.         Cnt++;
    7. }
    8. return n-Cnt;

    }

    int main()
    {

    1. while(cin>>n>>m>>s>>v)
    2. {
    3.     memset(To_Holes,0,sizeof(To_Holes));
    4.     for(int i=1;i<=n;i++)
    5.         cin>>Gopher[i].x>>Gopher[i].y;
    6.     for(int i=1;i<=m;i++)
    7.     {
    8.         cin>>Holes[i].x>>Holes[i].y;
    9.         for(int j=1;j<=n;j++)
    10.         {
    11.             double Dis=sqrt(pow(Holes[i].x-Gopher[j].x,2)+pow(Holes[i].y-Gopher[j].y,2));
    12.             if(Dis>v*s)
    13.                 Line[j][i]=false;   //找出每只鼠可以成功逃生的洞并标记
    14.             else
    15.                 Line[j][i]=true;
    16.         }
    17.     }
    18.     int Res=Hungarian();
    19.     cout<<Res<<endl;
    20. }
    21. return 0;

    }

发表评论

表情：
评论列表 （有 0 条评论，191人围观）

还没有评论，来说两句吧...

相关阅读

    相关 [二分图]最大匹配

    二分图的定义，以及判断图是否为二分图都很简单了。 现在要说二分图的最大匹配。 首先是定义吧，完美匹配就是一一对应，而最大匹配则是最大可以匹配的条数 完美匹配一定是最大匹配

    清疚清疚/ 0 赞/ 399 阅读