最小费用最大流的模板题
超级源点 m H 超级汇点
容量 1 1 1
费用 0 距离 0
#include<stdio.h> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<vector> #include<queue> using namespace std; #define MAXN 510 #define inf 1000000000 char z[MAXN][MAXN]; int S,T,cnt; int head[MAXN]; int x2[MAXN],y2[MAXN],x3[MAXN],y3[MAXN]; queue<int>q1; struct edg { int fr,to,w,next,co; }edge[200000]; void add(int u,int v,int w ,int cos) { edge[cnt].fr=u; edge[cnt].to=v; edge[cnt].w=w; edge[cnt].next=head[u]; edge[cnt].co=cos; head[u]=cnt++; } bool vis[MAXN]; int pre[MAXN],dis[MAXN]; bool spfa() { memset(vis,0,sizeof(vis)); memset(pre,-1,sizeof(pre)); for(int i=0;i<=T;i++) dis[i]=inf; dis[S]=0; q1.push(S); vis[S]=1; while(!q1.empty()) { int now = q1.front(); q1.pop(); vis[now]=0; for(int i=head[now];i!=-1;i=edge[i].next) { if(edge[i].w>0) { int v=edge[i].to; if(dis[v]>dis[now]+edge[i].co) { dis[v]=dis[now]+edge[i].co; pre[v]=i; if(!vis[v]) { vis[v]=1; q1.push(v); } } } } } return dis[T]!=inf; } int MCMF() { int ans=0; int flow_sum=0; while(spfa()) { int flow = inf; for(int i=pre[T];i!=-1;i=pre[edge[i].fr]) if(edge[i].w<flow) flow = edge[i].w; for(int i=pre[T];i!=-1;i=pre[edge[i].fr]) { edge[i].w-=flow; edge[i^1].w+=flow; } ans += dis[T]; flow_sum += flow; } return ans; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0) break; int c1,c2; c1=c2=0; for(int i=1;i<=n;i++) { scanf("%s",z[i]); for(int j=0;j<m;j++) { if(z[i][j]=='m') { x2[c1]=i; y2[c1++]=j; } else if(z[i][j]=='H') { x3[c2]=i; y3[c2++]=j; } } } cnt=0; S=0; T=c1+c2+1; memset(head,-1,sizeof(head)); for(int i=1;i<=c1;i++) { add(S,i,1,0); // 点 点 流量 费用 add(i,S,0,0); } for(int i=0;i<c1;i++) { for(int j=0;j<c2;j++) { int a=i+1; int b=j+1+c1; add(a,b,1,abs(x2[i]-x3[j])+abs(y2[i]-y3[j])); add(b,a,0,-(abs(x2[i]-x3[j])+abs(y2[i]-y3[j]))); } } for(int i=c1+1;i<=c1+c2;i++) { add(i,T,1,0); add(T,i,0,0); } int ans=0; ans = MCMF(); printf("%d ",ans); } return 0; }