程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU_1533 Going Home(最優匹配)

HDU_1533 Going Home(最優匹配)

編輯:C++入門知識

HDU_1533 Going Home(最優匹配)


說實話,這個題目剛開始還真看不出是完備匹配下的最大權匹配(當然,這個也可以用網絡流做。(應該是添加源點、匯點,源點到每個m的距離取m到所有H中最小的那個(用一個大數減掉後就是最大的)匯點到每個H的距離類似,然後求最大流) 有空再試著做一下吧,空說無益)。 我是在圖論500題裡看到的,在網絡流基礎題裡面。一開始想不出這個怎麼流! 後面網上查這個是二分圖最優匹配。於是昨天花幾個小時看了相關資料,寫了個比這題更水的 HDU2255。 今天寫這題的時候明顯輕松了。而且還想到用網絡流的做法。發現網絡流和二分匹配還是有聯系的。

  1. #include
  2. #include
  3. #include
  4. #include
  5. #include
  6. #include
  7. #define MAXN 105
  8. using namespace std;
  9.  
  10. int n,m,numm,numh;
  11. int map[MAXN][MAXN],lx[MAXN],ly[MAXN],vx[MAXN],vy[MAXN],matchy_x[MAXN];
  12. char s[MAXN][MAXN];
  13. int abs(int a){return a<0?-a:a;}
  14.  
  15. bool hungary(int u)
  16. {
  17. int i;
  18. vx[u]=1;
  19. for(i=0;i {
  20. if(vy[i] || map[u][i]!=lx[u]+ly[i]) continue;
  21. vy[i]=1;
  22. if(matchy_x[i]==-1 || hungary(matchy_x[i]))
  23. {
  24. matchy_x[i]=u;
  25. return 1;
  26. }
  27. }
  28. return 0;
  29. }
  30.  
  31. void EK_match()
  32. {
  33. int i,j;
  34. for(i=0;i {
  35. int maxx=0;
  36. for(j=0;j if(map[i][j]>maxx) maxx=map[i][j];
  37. lx[i]=maxx;
  38. }
  39. for(i=0;i {
  40. while(1)
  41. {
  42. memset(vx,0,sizeof(vx));
  43. memset(vy,0,sizeof(vy));
  44. if(hungary(i))
  45. break;
  46. else
  47. {
  48. int temp=INT_MAX;
  49. for(j=0;j for(int k=0;k if(!vy[k] && temp>lx[j]+ly[k]-map[j][k])
  50. temp=lx[j]+ly[k]-map[j][k];
  51. for(j=0;j {
  52. if(vx[j]) lx[j]-=temp;
  53. if(vy[j]) ly[j]+=temp;
  54. }
  55. }
  56. }
  57. }
  58. }
  59.  
  60. int main()
  61. {
  62. int i,j;
  63. while(scanf(%d%d,&n,&m)!=EOF && (n||m))
  64. {
  65. for(i=0;i scanf(%s,s[i]);
  66. numm=0;
  67. for(i=0;i {
  68. for(j=0;j {
  69. if(s[i][j]=='m')
  70. {
  71. numh=0;
  72. for(int k=0;k {
  73. for(int l=0;l {
  74. if(s[k][l]=='H')
  75. map[numm][numh++]=300-(abs(i-k)+abs(j-l));
  76. }
  77. }
  78. numm++;
  79. }
  80. }
  81. }
  82. memset(matchy_x,-1,sizeof(matchy_x));
  83. EK_match();
  84. int ans=0;
  85. for(i=0;i ans+=(300-map[matchy_x[i]][i]);
  86. printf(%d ,ans);
  87. }
  88. return 0;
  89. }
    以下是slack數組優化的:

     

     

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #define MAXN 105
    8. using namespace std;
    9.  
    10. int n,m,numm,numh;
    11. int map[MAXN][MAXN],lx[MAXN],ly[MAXN],vx[MAXN],vy[MAXN],matchy_x[MAXN],slack[MAXN];
    12. char s[MAXN][MAXN];
    13. int abs(int a){return a<0?-a:a;}
    14. int min(int a,int b) {return a
    15. bool hungary(int u)
    16. {
    17. int i;
    18. vx[u]=1;
    19. for(i=0;i {
    20. if(vy[i]) continue;
    21. if(map[u][i]==lx[u]+ly[i])
    22. {
    23. vy[i]=1;
    24. if(matchy_x[i]==-1 || hungary(matchy_x[i]))
    25. {
    26. matchy_x[i]=u;
    27. return 1;
    28. }
    29. }
    30. else slack[i]=min(slack[i],lx[u]+ly[i]-map[u][i]);
    31. }
    32. return 0;
    33. }
    34.  
    35. void EK_match()
    36. {
    37. int i,j;
    38. for(i=0;i {
    39. int maxx=0;
    40. for(j=0;j if(map[i][j]>maxx) maxx=map[i][j];
    41. lx[i]=maxx;
    42. }
    43. for(i=0;i {
    44. memset(slack,127,sizeof(slack));
    45. while(1)
    46. {
    47. memset(vx,0,sizeof(vx));
    48. memset(vy,0,sizeof(vy));
    49. if(hungary(i))
    50. break;
    51. else
    52. {
    53. int temp=INT_MAX;
    54. for(j=0;j if(temp>slack[j]) temp=slack[j];
    55. for(j=0;j {
    56. if(vx[j]) lx[j]-=temp;
    57. if(vy[j]) ly[j]+=temp;
    58. else slack[j]-=temp;
    59. }
    60. }
    61. }
    62. }
    63. }
    64.  
    65.  
    66. int main()
    67. {
    68. int i,j;
    69. while(scanf(%d%d,&n,&m)!=EOF && (n||m))
    70. {
    71. for(i=0;i scanf(%s,s[i]);
    72. numm=0;
    73. for(i=0;i {
    74. for(j=0;j {
    75. if(s[i][j]=='m')
    76. {
    77. numh=0;
    78. for(int k=0;k {
    79. for(int l=0;l {
    80. if(s[k][l]=='H')
    81. map[numm][numh++]=300-(abs(i-k)+abs(j-l));
    82. }
    83. }
    84. numm++;
    85. }
    86. }
    87. }
    88. memset(matchy_x,-1,sizeof(matchy_x));
    89. EK_match();
    90. int ans=0;
    91. for(i=0;i ans+=(300-map[matchy_x[i]][i]);
    92. printf(%d ,ans);
    93. }
    94. return 0;
    95. }

       

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved