费用流模板（带权二分图匹配）——hdu1533

/* 带权二分图匹配 用费用流求，增加源点s 和 汇点t */ #include<bits/stdc++.h> using namespace std; #define maxn 10005 #define maxm 200005 struct Edge{int to,nxt,w,c;}e[maxm<<1]; int head[maxn],tot,n,m,s,t,ans,maxflow; char mp[maxn][maxn]; vector<pair<int,int> >M,H; void add(int u,int v,int w,int c){ e[tot].to=v;e[tot].w=w;e[tot].c=c;e[tot].nxt=head[u];head[u]=tot++; e[tot].to=u;e[tot].w=0;e[tot].c=-c;e[tot].nxt=head[v];head[v]=tot++; } int d[maxn],v[maxn],incf[maxn],pre[maxn]; bool spfa(){ queue<int>q; memset(d,0x3f,sizeof d); memset(v,0,sizeof v); q.push(s);d[s]=0;v[s]=1; incf[s]=1<<30; while(q.size()){ int x=q.front();q.pop();v[x]=0; for(int i=head[x];i!=-1;i=e[i].nxt){ int y=e[i].to; if(e[i].w==0)continue; if(d[y]>d[x]+e[i].c){ d[y]=d[x]+e[i].c; incf[y]=min(incf[x],e[i].w); pre[y]=i; if(!v[y])v[y]=1,q.push(y); } } } if(d[t]==0x3f3f3f3f)return false; return true; } void update(){ int x=t; while(x!=s){ int i=pre[x]; e[i].w-=incf[t]; e[i^1].w+=incf[t]; x=e[i^1].to; } maxflow+=incf[t]; ans+=d[t]*incf[t]; } void init(){ memset(head,-1,sizeof head); tot=ans=maxflow=0; M.clear();H.clear(); } int dis(pair<int,int> a,pair<int,int> b){ return abs(a.first-b.first)+abs(a.second-b.second); } int main(){ while(cin>>n>>m&&n){ init(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ scanf("\n%c",&mp[i][j]); if(mp[i][j]=='m') M.push_back(make_pair(i,j)); if(mp[i][j]=='H') H.push_back(make_pair(i,j)); } s=0,t=2*M.size()+1; for(int i=0;i<M.size();i++) add(s,i+1,1,0); for(int i=0;i<H.size();i++) add(i+1+M.size(),t,1,0); for(int i=0;i<M.size();i++) for(int j=0;j<H.size();j++) add(i+1,j+1+M.size(),1,dis(M[i],H[j])); while(spfa()) update(); cout<<ans<<'\n'; } }

 

转载于:https://www.cnblogs.com/zsben991126/p/10995890.html