[关闭]
@xzyxzy 2018-05-15T14:19:04.000000Z 字数 1227 阅读 748

匈牙利算法

图论


一、基本内容

博客:http://www.renfei.org/blog/bipartite-matching.html
主要在于增广路的理解

二、实现

一般是E遍搜索(DFS),一次搜索大约是V的复杂度,总共(点数乘边数)

三、适用范围

二分图匹配问题
然后如果不是二分图(奇环)的最大匹配要用带花树

四、题目

1、练基础

2、刷提高

五、做题经验

1、每次寻找增广路都要记得初始化used数组

  1. for(int i=1;i<=n;i++)
  2. {
  3. memset(used,0,sizeof(used));
  4. ans+=DFS(i);
  5. }

这是第二次敲模板时忽略的问题

2、想清楚题目是否可以用二分图,怎么用

对于酒店之王,要用两个二分图而且不能合并,合并会使得匹配数增加

附录

  1. //P3386模板
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. using namespace std;
  7. const int N=1001;
  8. bool used[N],f[N][N];
  9. int match[N],n,m,e,ans=0;
  10. bool DFS(int pos)
  11. {
  12. for(int i=1;i<=m;i++)
  13. {
  14. if(used[i]||!f[pos][i])continue;
  15. used[i]=1;
  16. if(!match[i]||DFS(match[i]))
  17. {
  18. match[i]=pos;
  19. return 1;
  20. }
  21. }
  22. return 0;
  23. }
  24. int main()
  25. {
  26. scanf("%d%d%d",&n,&m,&e);
  27. for(int i=1;i<=e;i++)
  28. {
  29. int x,y;scanf("%d%d",&x,&y);
  30. if(x<=n&&y<=m)f[x][y]=1;
  31. }
  32. for(int i=1;i<=n;i++)
  33. {
  34. memset(used,0,sizeof(used));
  35. ans+=DFS(i);
  36. }
  37. printf("%d\n",ans);
  38. return 0;
  39. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注