BFS實現，O(n^3)
1 #include <iostream>
2 using namespace std;
3 const int SIZE=110;
4 const int INF=0x7fffffff;
5 int w[SIZE][SIZE],lx[SIZE],ly[SIZE],sx,sy;
6 int match[SIZE],pax[SIZE],pay[SIZE],slack[SIZE];
7 bool x[SIZE],y[SIZE];
8 int N,M;
9 struct Coord{
10 int r,c;
11 };
12
13 inline void clear(){
14 memset(x,0,sizeof(x));
15 memset(y,0,sizeof(y));
16 memset(pax,0,sizeof(pax));
17 memset(pay,0,sizeof(pay));
18 fill(slack,slack+SIZE,INF);
19 }
20
21 bool bfs(int r){
22 int i,j,k;
23 int tag,que[SIZE*2],pq=0,sq=1;
24 que[0]=r<<1; x[r]=true;
25 while(pq<sq){
26 tag=que[pq]&1; k=que[pq]>>1;
27 if(tag==0){//look for the start vex of bolt edge
28 for(i=1;i<=sy;i++){
29 if(y[i])continue;
30 if(lx[k]+ly[i]==w[k][i]){
31 y[i]=true; pay[i]=k;
32 if(!match[i]){ //agument
33 for(j=i;j;j=pax[pay[j]]){
34 match[j]=pay[j];
35 }
36 return true;
37 }
38 else{
39 que[sq++]=(i<<1)|(tag^1);
40 }
41 }
42 else{
43 slack[i]=min(slack[i],lx[k]+ly[i]-w[k][i]);
44 }
45 }
46 }
47 else{ //go along its matched edge!
48 x[match[k]]=true;
49 pax[match[k]]=k;
50 que[sq++]=(match[k]<<1)|(tag^1);
51 }
52 pq++;
53 }
54 return false;
55 }
56
57 int solve(){
58 int i,j,k;
59 memset(lx,0,sizeof(lx));
60 memset(ly,0,sizeof(ly));
61 memset(match,0,sizeof(match));
62
63 for(i=1;i<=sx;i++){
64 for(j=1;j<=sy;j++){
65 lx[i]=max(lx[i],w[i][j]);
66 }
67 }
68 clear();
69 for(i=1;i<=sx;i++){
70 int r=i;
71 while(1){
72 if(bfs(r)){
73 clear();
74 break;
75 }
76 int d=INF,ty;
77 for(j=1;j<=sy;j++){
78 if(!y[j] && slack[j]<d){
79 d=slack[j];
80 ty=j;
81 }
82 }
83 for(j=1;j<=sx;j++){
84 if(x[j]){
85 lx[j]-=d;
86 if(lx[j]+ly[ty]==w[j][ty]){ //look for ty's rear v in X
87 r=j; //reuse search tree of last bfs
88 }
89 }
90 }
91 for(j=1;j<=sy;j++){
92 if(y[j]){
93 ly[j]+=d;
94 }
95 slack[j]-=d;
96 }
97 }
98 }
99 int ans=0;
100 for(i=1;i<=sy;i++){
101 ans+=SIZE*2-w[match[i]][i];
102 }
103 return ans;
104 }
105
106 int main(){
107 //freopen("out_b3.txt","w",stdout);
108 int i,j;
109 char str[SIZE];
110 Coord cx[SIZE],cy[SIZE];
111 while(scanf("%d%d\n",&N,&M)!=EOF && M*N){
112 memset(w,0,sizeof(w));
113 sx=0;sy=0;
114 for(i=0;i<N;i++){
115 gets(str);
116 for(j=0;j<M;j++){
117 if(str[j]=='H'){
118 sy++;
119 cy[sy].r=i;
120 cy[sy].c=j;
121 }
122 else if(str[j]=='m'){
123 sx++;
124 cx[sx].r=i;
125 cx[sx].c=j;
126 }
127 }
128 }
129 for(i=1;i<=sx;i++){
130 for(j=1;j<=sy;j++){
131 w[i][j]=SIZE*2-(abs(cx[i].r-cy[j].r)+abs(cx[i].c-cy[j].c));
132 }
133 }
134 printf("%d\n",solve());
135 }
136 return 0;
137 }
DFS實現，O(n^4)
1 #include <iostream>
2 using namespace std;
3 const int SIZE=110;
4 const int INF=0x7fffffff;
5 int w[SIZE][SIZE],lx[SIZE],ly[SIZE],sx,sy,match[SIZE];
6 bool x[SIZE],y[SIZE];
7 int N,M;
8 struct Coord{
9 int r,c;
10 };
11
12 bool dfs(int k){
13 x[k]=true;
14 for(int i=1;i<=sy;i++){
15 if(!y[i] && lx[k]+ly[i]==w[k][i]){
16 y[i]=true;
17 if(!match[i] || dfs(match[i])){
18 match[i]=k;
19 return true;
20 }
21 }
22 }
23 return false;
24 }
25
26 int solve(){
27 int i,j,k;
28 memset(ly,0,sizeof(ly));
29 memset(lx,0,sizeof(lx));
30 memset(match,0,sizeof(match));
31 for(i=1;i<=sx;i++){
32 for(j=1;j<=sy;j++){
33 lx[i]=max(lx[i],w[i][j]);
34 }
35 }
36 for(i=1;i<=sx;i++){
37 while(1){
38 memset(x,0,sizeof(x));
39 memset(y,0,sizeof(y));
40 if(dfs(i))break;
41 int d=INF;
42 for(j=1;j<=sx;j++){
43 if(x[j]){
44 for(k=1;k<=sy;k++){
45 if(!y[k]){
46 d=min(d,lx[j]+ly[k]-w[j][k]);
47 }
48 }
49 }
50 }
51 for(j=1;j<=sx;j++){
52 if(x[j]) lx[j]-=d;
53 }
54 for(j=1;j<=sy;j++){
55 if(y[j]) ly[j]+=d;
56 }
57 }
58 }
59 int ans=0;
60 for(i=1;i<=sy;i++){
61 ans+=SIZE*2-w[match[i]][i];
62 }
63 return ans;
64 }
65
66 int main(){
67 int i,j;
68 char str[SIZE];
69 Coord cx[SIZE],cy[SIZE];
70 while(scanf("%d%d\n",&N,&M)!=EOF && M*N){
71 memset(w,0,sizeof(w));
72 sx=0;sy=0;
73 for(i=0;i<N;i++){
74 gets(str);
75 for(j=0;j<M;j++){
76 if(str[j]=='H'){
77 sy++;
78 cy[sy].r=i;
79 cy[sy].c=j;
80 }
81 else if(str[j]=='m'){
82 sx++;
83 cx[sx].r=i;
84 cx[sx].c=j;
85 }
86 }
87 }
88 for(i=1;i<=sx;i++){
89 for(j=1;j<=sy;j++){
90 w[i][j]=SIZE*2-(abs(cx[i].r-cy[j].r)+abs(cx[i].c-cy[j].c));
91 }
92 }
93
94 printf("%d\n",solve());
95 }
96 return 0;
97 }
posted on 2009-02-15 22:10
wolf5x 閱讀(320)
評論(0) 編輯 收藏 引用 所屬分類:
acm_icpc