锐客网

  1. 首页 > it技术 > >

二分图匹配（附算法简介）（例题（|二分图匹配（附算法简介）（例题： 囊地鼠））

这是一种神奇的算法。
它所解决的问题就是：
对于一个图，图上只有黑点和白点，黑点和白点之间有连边，问黑点和白点的最大匹配数是多少。
讲完问题，我们来讲讲算法。
首先我们要先找到目前没有被匹配的第一个黑色点（此算法可以只做一边（黑或白））
然后我们找到与他连边的点，并把这两个点标记为一个匹配。
然后我们一直往下找，直到找到一个点，这个点连向的是已经被匹配过的点（记为V）。
那么我们此时就尝试能否让原来与V节点匹配的点找到另一个未匹配的节点，来替代它（此时需要递归，因为有可能找到的点也是被匹配过的。）
那么如果这个点能够被匹配，那么就修改，否则就不能匹配这个点。
由于我们知道，如果这个点匹配失败了，那么下次再匹配到这个点，就可以直接跳过了（优化）
下面我们贴上例题
————————————————我是分割线————————————————
题目描述 囊地鼠家族一共有n只囊地鼠，为了逃避捕食者的袭击，它们在地上挖了m个洞。当猎食者到达的时候，它们必须在s的时间内跑到洞中。但是由于洞的大小有限，每个洞只能躲藏1只囊地鼠。所有囊地鼠的跑步速度都为v。留在洞外的囊地鼠就会被吃掉。囊地鼠家族要计划一个逃生计划，让尽可能多的囊地鼠逃生。
输入 输入文件包含多个数据，每个数据的第一行包括4个小于100的整数：n,m,s,v。以下n行给出每只囊地鼠的位置坐标，然后的m行给出洞的坐标。
输出 对于每个数据输出无法逃生的囊地鼠的个数。
【二分图匹配（附算法简介）（例题（|二分图匹配（附算法简介）（例题： 囊地鼠））】————————————————我是分割线————————————————
这道题显然就是二分图匹配，只要判断一下如果第i只地鼠能够跑到第j个坑里，那么就从i向j连边
下面贴代码

#include #include #include #define eps 1e-9 #define MN 101 #define M 10001 using namespace std; int n,m,s,v,ans,num; struct edge{ int to,next; }g[M]; int head[MN],lky[MN]; bool vis[MN]; double maxdis=0; double x[MN],y[MN]; double dist(double a,double b,double c,double d){return (double)sqrt((b-a)*(b-a)+(d-c)*(d-c)); } void ins(int u,int v){g[++num].next=head[u]; head[u]=num; g[num].to=v; } bool match(int u){ for(int i=head[u]; i; i=g[i].next) if(!vis[g[i].to]){ vis[g[i].to]=1; if(!lky[g[i].to]||match(lky[g[i].to])){ lky[g[i].to]=u; return true; } } return false; } int main(){ while(scanf("%d%d%d%d",&n,&m,&s,&v)!=EOF){ maxdis=1.0*s*v; ans=num=0; double qx,qy; memset(head,0,sizeof(head)); for(int i=1; i<=n; i++)scanf("%lf%lf",&x[i],&y[i]); for(int i=1; i<=m; i++){ scanf("%lf%lf",&qx,&qy); for(int j=1; j<=n; j++) if(dist(x[j],qx,y[j],qy)+eps

转载于:https://www.cnblogs.com/ghostfly233/p/7119005.html

    推荐阅读


    上一篇：蝗虫算法java代码_蝗虫优化算法及应用研究

    下一篇：基于matlab的捕食算法,【优化求解】基于matlab细菌觅食算法的函数优化分析【含Matlab源码 217期】...