题意：二分图最小权匹配。
构图：S向左边的点连容量1，费用0的边，右边的点向T连容量1，费用0的边，点之间连容量1，费用为边权的边。最小费用最大流。
注意:
1.100*100的方格中有10000个点,数组要开大;
2.n==0 && m==0 时结束。
View Code
View Code /*Source Code Problem: 2195 User: HEU_daoguang Memory: 1172K Time: 94MS Language: G++ Result: Accepted Source Code */ #include <iostream> #include <stdio.h> #include <queue> #include <math.h> #include <string.h> using namespace std; #define V 6005 #define E 10010000 #define inf 999999999 int n,m; char map[102][102]; int hp[V][2],mp[V][2]; int vis[V]; int dist[V]; int pre[V]; struct Edge{ int u,v,c,cost,next; }edge[E]; int head[V],cnt; void init(){ cnt=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int c,int cost){ edge[cnt].u=u;edge[cnt].v=v;edge[cnt].cost=cost; edge[cnt].c=c;edge[cnt].next=head[u];head[u]=cnt++; edge[cnt].u=v;edge[cnt].v=u;edge[cnt].cost=-cost; edge[cnt].c=0;edge[cnt].next=head[v];head[v]=cnt++; } bool spfa(int begin,int end){ int u,v; queue<int> q; for(int i=0;i<=end+2;i++){ pre[i]=-1; vis[i]=0; dist[i]=inf; } vis[begin]=1; dist[begin]=0; q.push(begin); while(!q.empty()){ u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=edge[i].next){ if(edge[i].c>0){ v=edge[i].v; if(dist[v]>dist[u]+edge[i].cost){ dist[v]=dist[u]+edge[i].cost; pre[v]=i; if(!vis[v]){ vis[v]=true; q.push(v); } } } } } return dist[end]!=inf; } int MCMF(int begin,int end){ int ans=0,flow; int flow_sum=0; while(spfa(begin,end)){ flow=inf; for(int i=pre[end];i!=-1;i=pre[edge[i].u]) if(edge[i].c<flow) flow=edge[i].c; for(int i=pre[end];i!=-1;i=pre[edge[i].u]){ edge[i].c-=flow; edge[i^1].c+=flow; } ans+=dist[end]*flow; flow_sum+=flow; } return ans; } int main() { //freopen("in.txt","r",stdin); while(scanf("%d%d",&n,&m)!=EOF){ if(n==0 && m==0) break; for(int i=0;i<n;i++){ scanf("%s",map[i]); } int hcnt=1,mcnt=1; for(int i=0;i<n;i++) for(int j=0;j<m;j++){ if(map[i][j]=='H'){ hp[hcnt][0]=i; hp[hcnt][1]=j; hcnt++; } if(map[i][j]=='m'){ mp[mcnt][0]=i; mp[mcnt][1]=j; mcnt++; } } hcnt--; mcnt--; init(); for(int i=1;i<=hcnt;i++){ addedge(0,i,1,0); //addedge(i,0,1,0); } for(int j=1;j<=mcnt;j++){ addedge(hcnt+j,hcnt+mcnt+1,1,0); //addedge(hcnt+mcnt+1,hcnt+j,1,0); } for(int i=1;i<=hcnt;i++) for(int j=1;j<=mcnt;j++){ addedge(i,hcnt+j,1,fabs(hp[i][0]-mp[j][0])+fabs(hp[i][1]-mp[j][1])); //addedge(hcnt+j,i,1,fabs(hp[i][0]-mp[j][0])+fabs(hp[i][1]-mp[j][1])); } int res=MCMF(0,hcnt+mcnt+1); printf("%d\n",res); } return 0; } /* 2 2 .m H. 5 5 HH..m ..... ..... ..... mm..H 7 8 ...H.... ...H.... ...H.... mmmHmmmm ...H.... ...H.... ...H.... 20 20 ..mm..H..H.H...HHH.m m.H...H.....H......m ..H...mm.........m.. Hm.m..H.H...H..m.... mH.Hm....mH........H m............m...... .m..H...........H..m H.m.H.....H.......m. ...m..Hm.....m.H...H ..H...H....H......mH ..m.m.....m....mm... ..........H.......H. ...mm......m...H.... .....m..H.H......m.m .H......mm.H.m.m.m.m HH..........HH..HH.. ...m..H........Hm... ....H.....H...mHm... H...........m......m ....m...H.m.....m... 20 20 ...Hm.m.HHH...Hmm... .H........m.......H. .......H...H.H...... ....HmH.m....Hm..m.. ....m..m............ H..H.........m....H. .m.H...m...mH.m..H.. .mH..H.H......m...m. ...mH...H.......m... ..Hm..H..H......m.m. ..mH...H.m..m.H..HH. m.m......m........m. ...mH..m.....mH..... ....m.H.H..........H ....H.......H....m.H H.mH.......m.......H ..............m.HH.H ..H.........m.m.m... .........mH.....mmm. ...mH.m.m.....H..m.. 20 20 H.H.......H....m.... .....m..H......H..H. ...H..............m. mH..mm..m...H....... ......H....mm.H..... .mH..mm.....mH.H...H .........HHH........ ......H.H...mm...... .m..m.H...mHmm...HH. mm..Hmm.H..m...m.H.m H.Hm.m.m.....m...... ...........m.......H ......m......H...m.. ....H..........Hm... .H..H.m....m........ ...H....Hm.......... m.H.mHm.m.m...H...H. .m..........m....... H......H...HmHHm..H. ..H..m.m...m.H..H... 20 20 .m..m..Hm........... .m..H.H...m.m.m...H. ........m..mH....H.. ..H...........Hm.H.m H..H.m........mm..m. H.......m........... ..m..Hmmmm...m..mH.. ..H.Hm...H.......... H....m.......mm..... ....m..m.....m.....m .H.m.H...H.....H.... .m........mm..H...H. ..m.......H.mH..mm.H .......Hm...HH....H. ...mm....HHH........ ..H.m..H........m... H.........H......... HH.H.....m.H..Hm.... ...H.m...H.Hm.....m. .H..mH..H..H........ 20 20 m.........m.......m. ..m.H....m....m...m. m...H.m.....H.H..... .....H.Hm.m...m..... ..mH...H.H.m.H...H.. H....H......m.....m. ..................H. .m..m.Hm......m..H.. ....H..H.m.....H...H ....m.H......m.H...m ....HH...H...H...... ..H.....m......H.H.. mmH...mmm.....m..... ..m.......m...mmH... ......H.H..m...Hm..H HHHm.H.m........H... ...mHm.......m....m. .....mmH.H..H.....m. ......m..H.....m...H ..HH..m...mH......H. 20 20 m.HHm..HH..m.mHm.... mm..H............... m...HH.......m.H.... ..mH.m.m.......mmH.. H.m........m.......H m.H....m....m..m...H ....m......mm....... .m.H....m..H..m..H.. H....m......H....... ...H...........m.m.H ......H...m...H..m.. .mH..H.H.....m...... ...m.....m.H...HmH.H m.......H..H.H..mm.H ...H.........Hm.HH.. .m....H.....m.HHm... ...HHH...........m.. m............H...... .....m..mm.....m.... .....m..H..H..H....H 20 20 ....H.............m. .....HH..mH..Hm..H.. m...........mH....mm ..m..m.H......m....m .H..........mHH....m ...........m..H.m... ..H...H.........mHm. ......H...........H. H.....H.....H..m.... H.H..H..m...m..mH.m. ....H...m.H.mHmm.mHm ..mmm...H....m....H. .........m..m....... .m.H....Hm....m..... .....H.......HH...mH ..H..H....m.m.....HH .Hm.............H... H...Hm.......H.m.m.. .....m..HH...H.....m ........mHmmH..m.... 20 20 .....H.......H...m.m .m..H.m.m....m...... m.H.HHH..mm......... H...mH.mH........... ..mHm..m.m......m..m H.HH.....m...m...... H.mH....H......H.... ...mH.m.mHmH...H.... ........H.....m..... ..H.......HmH...H... ......m...HH.m...... .H..m.H...H......... ...H...m..m..m...m.. .mH..HH......m...H.. ...m....H.H.H.m..... .........H.m........ ..m..H...H......H... mmH..mH.....m.H..H.. H....mm...H.m...m.mm ......m............. 20 20 ....mH..m...m.....m. ..m......mHm...H.... .H.....mHm....H..H.. ...HH..........m.m.. ..m..mm........m.... ...m.....H.......... ..mH..H...m......... ...H.H.....m..mH..m. ..H.........Hm.Hm..H ...........H......m. .............H...mm. H.m.....Hm.H.m...... ....Hm..m..mm.H...m. ...H.H.H......H.Hm.. H.m............m.... ..mH.m.m...m..H.m..H HH.H....m.H..H...m.. .....H.....H...H...H ........mH.HHm.....m .H.H.....mmH......m. 20 20 .mH........m.mmH..H. m....H........H..H.. .........Hm.m.m..... ....H.H...m......... .H....m............. HH.....H.....H.HH... mmmmmm.H..m..m...... .Hm.H...H.H..m.H.... .........m..m.mHmHH. ...m.m....m..H.Hm..H ...Hm....H..m....m.. ...mH.....m.......m. .H...HmmH..H.....H.. m.H...m.....mmH....H .m.H......m...H..... H........m..Hm...... .......m...........m ...m........m...H... .........m...H...... HH..H..m...H......H. */