HDU_1533 Going Home（最優匹配）

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. }