題意：二分圖最小權匹配。

構圖：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. */

?

?

轉載于:https://www.cnblogs.com/markliu/archive/2012/05/23/2514644.html

總結

以上是生活随笔為你收集整理的POJ-2195(最小费用最大流)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。