Going Home
题意：给出地图，其中m和h个数相等，求所有m到h的总路程最短。
KM
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int inf=0x3f3f3f3f; 4 const int maxn=110; 5 6 int eg[maxn],eb[maxn],vg[maxn],vb[maxn]; 7 int mc[maxn],slack[maxn]; 8 int mx[maxn],my[maxn],hx[maxn],hy[maxn]; 9 int c[maxn][maxn]; 10 char g[maxn]; 11 int n,m; 12 int ct; 13 int dfs(int id) 14 { 15 vg[id]=1; 16 for(int i=0;i<ct;i++) 17 { 18 if(vb[i]==1) continue; 19 int gap=eg[id]+eb[i]-c[id][i]; 20 if(gap==0) 21 { 22 vb[i]=1; 23 if(mc[i]==-1||dfs(mc[i])){ 24 mc[i]=id; 25 return 1; 26 } 27 } 28 else{ 29 slack[i]=min(slack[i],gap); 30 } 31 } 32 return 0; 33 } 34 void KM() 35 { 36 memset(mc,-1,sizeof(mc)); 37 memset(eb,0,sizeof(eb)); 38 for(int i=0;i<ct;i++){ 39 eg[i]=c[i][0]; 40 for(int j=0;j<ct;j++) eg[i]=max(eg[i],c[i][j]); 41 } 42 for(int i=0;i<ct;i++){ 43 memset(slack,inf,sizeof(slack)); 44 while(1){ 45 memset(vb,0,sizeof(vb)); 46 memset(vg,0,sizeof(vg)); 47 if(dfs(i)) break; 48 int d=inf; 49 for(int i=0;i<ct;i++) if(!vb[i]) d=min(d,slack[i]); 50 for(int i=0;i<ct;i++){ 51 if(vg[i]) eg[i]-=d; 52 if(vb[i]) eb[i]+=d; 53 else slack[i]-=d; 54 } 55 } 56 } 57 } 58 int main(){ 59 while(scanf("%d%d",&n,&m)&&(n||m)){ 60 memset(c,-inf,sizeof(0)); 61 int cth=0,ctm=0; 62 for(int i=0;i<n;i++){ 63 scanf("%s",g); 64 for(int j=0;j<m;j++){ 65 if(g[j]=='H') {hx[cth]=i;hy[cth++]=j;} 66 if(g[j]=='m') {mx[ctm]=i;my[ctm++]=j;} 67 } 68 } 69 ct=cth; 70 for(int i=0;i<ct;i++) 71 for(int j=0;j<ct;j++){ 72 c[i][j]=-abs(mx[i]-hx[j])-abs(my[i]-hy[j]); //m到H的距离 73 } 74 KM(); 75 int ans=0; 76 for(int i=0;i<ct;i++) 77 ans+=c[mc[i]][i]; 78 printf("%d ",-ans); 79 } 80 }
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int inf=0x3f3f3f3f; 4 const int maxn=110; 5 6 int eg[maxn],eb[maxn],vg[maxn],vb[maxn]; 7 int mc[maxn],d; 8 int mx[maxn],my[maxn],hx[maxn],hy[maxn]; 9 int c[maxn][maxn]; 10 char g[maxn]; 11 int n,m; 12 int ct; 13 int dfs(int id){ 14 vg[id]=1; 15 for(int i=0;i<ct;i++){ 16 if(vb[i]==1) continue; 17 int gap=eg[id]+eb[i]-c[id][i]; 18 if(gap==0){ 19 vb[i]=1; 20 if(mc[i]==-1||dfs(mc[i])){ 21 mc[i]=id; 22 return 1; 23 } 24 } 25 else{ 26 d=min(d,gap); 27 } 28 } 29 return 0; 30 } 31 void KM(){ 32 memset(mc,-1,sizeof(mc)); 33 memset(eb,0,sizeof(eb)); 34 for(int i=0;i<ct;i++){ 35 eg[i]=c[i][0]; 36 for(int j=0;j<ct;j++) eg[i]=max(eg[i],c[i][j]); 37 } 38 for(int i=0;i<ct;i++){ 39 while(1){ 40 memset(vb,0,sizeof(vb)); 41 memset(vg,0,sizeof(vg)); 42 d=inf; 43 if(dfs(i)) break; 44 for(int i=0;i<ct;i++){ 45 if(vg[i]) eg[i]-=d; 46 if(vb[i]) eb[i]+=d; 47 } 48 } 49 } 50 } 51 int main(){ 52 while(scanf("%d%d",&n,&m)&&(n||m)){ 53 memset(c,-inf,sizeof(0)); 54 int cth=0,ctm=0; 55 for(int i=0;i<n;i++){ 56 scanf("%s",g); 57 for(int j=0;j<m;j++){ 58 if(g[j]=='H') {hx[cth]=i;hy[cth++]=j;} 59 if(g[j]=='m') {mx[ctm]=i;my[ctm++]=j;} 60 } 61 } 62 ct=cth; 63 for(int i=0;i<ct;i++) 64 for(int j=0;j<ct;j++) 65 c[i][j]=-abs(mx[i]-hx[j])-abs(my[i]-hy[j]); //m到H的距离 66 KM(); 67 int ans=0; 68 for(int i=0;i<ct;i++) ans+=c[mc[i]][i]; 69 printf("%d ",-ans); 70 } 71 }