[关闭]
@KirinBill 2017-11-12T12:14:26.000000Z 字数 4888 阅读 1182

KM算法学习笔记

学习笔记 二分图

目录


最佳完美匹配

对于一个有完美匹配的二分图,将其中的边都赋了一个边权(可以为负),其中边权和最大的完美匹配叫做该二分图的最佳完美匹配。

某个不知名的定理

一些约定:

  1. 这里讨论的二分图都指有完美匹配的二分图;
  2. 记二分图左边的点集为,右边的为
  3. 连接的边记为,其权值记为
  4. 形如的都是对于某个点而言的一些值。
  5. 对于一个二分图的两个点集,我们给每个点分配一个顶标,记为

定理:


算法实现

可行顶标与松弛变量

代码

  1. int n;
  2. int G[MAXN][MAXN],lx[MAXN],ly[MAXN],slack[MAXN],match[MAXN];
  3. bool visx[MAXN],visy[MAXN];
  4. bool Hungary(int x){
  5. visx[x]=true;
  6. for(int y=1,dta;y<=n;++y){
  7. dta=lx[x]+ly[y]-G[x][y];
  8. if(!visy[y] && dta==0){
  9. visy[y]=true;
  10. if(!match[y] || Hungary(match[y])){
  11. match[y]=x;
  12. return true;
  13. }
  14. }
  15. else slack[y]=min(slack[y],dta);
  16. }
  17. return false;
  18. }
  19. inline int KM(){
  20. for(int i=1;i<=n;++i){
  21. for(int j=1;j<=n;++j)
  22. lx[i]=max(lx[i],G[i][j]);
  23. }
  24. for(int x=1,d;x<=n;++x){
  25. memset(visx,false,sizeof(visx));
  26. memset(visy,false,sizeof(visy));
  27. memset(slack,0x7f,sizeof(slack));
  28. while(!Hungary(x)){
  29. d=INT_MAX;
  30. for(int y=1;y<=n;++y){
  31. if(!visy[y]) d=min(d,slack[y]);
  32. }
  33. for(int i=1;i<=n;++i){
  34. if(visx[i]){
  35. lx[i]-=d;
  36. visx[i]=false;
  37. }
  38. if(visy[i]){
  39. ly[i]+=d;
  40. visy[i]=false;
  41. }
  42. }
  43. }
  44. }
  45. int ret=0;
  46. for(int i=1;i<=n;++i)
  47. ret+=lx[i]+ly[i];
  48. return ret;
  49. }

练习

[HDU 2255] 奔小康赚大钱

代码:

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <climits>
  4. #include <cstring>
  5. using std::min;
  6. using std::max;
  7. const int MAXN=305;
  8. int n;
  9. int lx[MAXN],ly[MAXN],G[MAXN][MAXN],slack[MAXN],match[MAXN];
  10. bool visx[MAXN],visy[MAXN];
  11. bool Hungary(int x){
  12. visx[x]=true;
  13. for(int y=1,dta;y<=n;++y){
  14. dta=lx[x]+ly[y]-G[x][y];
  15. if(!visy[y] && dta==0){
  16. visy[y]=true;
  17. if(!match[y] || Hungary(match[y])){
  18. match[y]=x;
  19. return true;
  20. }
  21. }
  22. else slack[y]=min(slack[y],dta);
  23. }
  24. return false;
  25. }
  26. inline int KM(){
  27. memset(lx,0,sizeof(lx));
  28. memset(ly,0,sizeof(ly));
  29. memset(match,0,sizeof(match));
  30. for(int x=1;x<=n;++x){
  31. for(int y=1;y<=n;++y)
  32. lx[x]=max(lx[x],G[x][y]);
  33. }
  34. for(int x=1,d;x<=n;++x){
  35. memset(slack,0x7f,sizeof(slack));
  36. memset(visx,false,sizeof(visx));
  37. memset(visy,false,sizeof(visy));
  38. while(!Hungary(x)){
  39. d=INT_MAX;
  40. for(int y=1;y<=n;++y){
  41. if(!visy[y]) d=min(d,slack[y]);
  42. }
  43. for(int i=1;i<=n;++i){
  44. if(visx[i]){
  45. lx[i]-=d;
  46. visx[i]=false;
  47. }
  48. if(visy[i]){
  49. ly[i]+=d;
  50. visy[i]=false;
  51. }
  52. }
  53. }
  54. }
  55. int ret=0;
  56. for(int i=1;i<=n;++i)
  57. ret+=lx[i]+ly[i];
  58. return ret;
  59. }
  60. int main(){
  61. while(scanf("%d",&n)!=EOF){
  62. for(int i=1;i<=n;++i){
  63. for(int j=1;j<=n;++j)
  64. scanf("%d",&G[i][j]);
  65. }
  66. printf("%d\n",KM());
  67. }
  68. return 0;
  69. }

[UVa 11383] Golden Tiger Claw

代码:

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <climits>
  5. using std::min;
  6. using std::max;
  7. const int MAXN=505;
  8. int n;
  9. int G[MAXN][MAXN],lx[MAXN],ly[MAXN],slack[MAXN],match[MAXN];
  10. bool visx[MAXN],visy[MAXN];
  11. bool Hungary(int x){
  12. visx[x]=true;
  13. for(int y=1,dta;y<=n;++y){
  14. dta=lx[x]+ly[y]-G[x][y];
  15. if(!visy[y] && dta==0){
  16. visy[y]=true;
  17. if(!match[y] || Hungary(match[y])){
  18. match[y]=x;
  19. return true;
  20. }
  21. }
  22. else slack[y]=min(slack[y],dta);
  23. }
  24. return false;
  25. }
  26. inline int KM(){
  27. memset(lx,-0x7f,sizeof(lx));
  28. memset(ly,0,sizeof(ly));
  29. memset(match,0,sizeof(match));
  30. for(int i=1;i<=n;++i){
  31. for(int j=1;j<=n;++j)
  32. lx[i]=max(lx[i],G[i][j]);
  33. }
  34. for(int x=1,d;x<=n;++x){
  35. memset(visx,false,sizeof(visx));
  36. memset(visy,false,sizeof(visy));
  37. memset(slack,0x7f,sizeof(slack));
  38. while(!Hungary(x)){
  39. d=INT_MAX;
  40. for(int y=1;y<=n;++y){
  41. if(!visy[y]) d=min(d,slack[y]);
  42. }
  43. for(int i=1;i<=n;++i){
  44. if(visx[i]){
  45. lx[i]-=d;
  46. visx[i]=false;
  47. }
  48. if(visy[i]){
  49. ly[i]+=d;
  50. visy[i]=false;
  51. }
  52. }
  53. }
  54. }
  55. int ret=0;
  56. for(int i=1;i<=n;++i)
  57. ret+=lx[i]+ly[i];
  58. return ret;
  59. }
  60. int main(){
  61. int ans;
  62. while(scanf("%d",&n)!=EOF){
  63. memset(G,0,sizeof(G));
  64. for(int i=1;i<=n;++i){
  65. for(int j=1;j<=n;++j)
  66. scanf("%d",&G[i][j]);
  67. }
  68. ans=KM();
  69. for(int i=1;i<=n;++i)
  70. printf("%d ",lx[i]);
  71. putchar('\n');
  72. for(int i=1;i<=n;++i)
  73. printf("%d ",ly[i]);
  74. putchar('\n');
  75. printf("%d\n",ans);
  76. }
  77. return 0;
  78. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注