费用流水题 照着图建图直接搞
#include<iostream>#include<cstring>#include<cstdio>#include<queue>#include<cmath>using namespace std;const int max_n=105;const int max_m=105;const int max_N=max_n*2+2;const int max_M=max_n*max_n+max_n*2;const int max_e=max_M*2;const int inf=1e9;char ch;int n,m,maxflow,mincost,cntman,cnthome,N,dollar;int point[max_N],next[max_e],v[max_e],remain[max_e],c[max_e],tot;int last[max_N],dis[max_N];bool vis[max_N];queue <int> q;struct hp{ int l,r;}man[max_n],home[max_n];inline void clear(){ tot=-1; memset(point,-1,sizeof(point)); memset(next,-1,sizeof(next)); memset(v,0,sizeof(v)); memset(remain,0,sizeof(remain)); memset(c,0,sizeof(c)); memset(last,0,sizeof(last)); memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); while (!q.empty()) q.pop(); for (int i=1;i<=cntman;++i) man[i].l=man[i].r=0; for (int i=1;i<=cnthome;++i) home[i].l=home[i].r=0; cntman=cnthome=N=maxflow=mincost=0;}inline void addedge(int x,int y,int cap,int z){ ++tot; next[tot]=point[x]; point[x]=tot; v[tot]=y; remain[tot]=cap; c[tot]=z; ++tot; next[tot]=point[y]; point[y]=tot; v[tot]=x; remain[tot]=0; c[tot]=-z;}inline int addflow(int s,int t){ int ans=inf,now=t; while (now!=s){ ans=min(ans,remain[last[now]]); now=v[last[now]^1]; } now=t; while (now!=s){ remain[last[now]]-=ans; remain[last[now]^1]+=ans; now=v[last[now]^1]; } return ans;}inline bool bfs(int s,int t){ memset(dis,0x7f,sizeof(dis)); memset(vis,0,sizeof(vis)); dis[s]=0; vis[s]=true; while (!q.empty()) q.pop(); q.push(s); while (!q.empty()){ int now=q.front(); q.pop(); vis[now]=false; for (int i=point[now];i!=-1;i=next[i]) if (dis[v[i]]>dis[now]+c[i]&&remain[i]){ dis[v[i]]=dis[now]+c[i]; last[v[i]]=i; if (!vis[v[i]]){ vis[v[i]]=true; q.push(v[i]); } } } if (dis[t]>inf) return false; int flow=addflow(s,t); maxflow+=flow; mincost+=flow*dis[t]; return true;}inline void major(int s,int t){ maxflow=0; mincost=0; while (bfs(s,t));}int main(){ while (~scanf("%d%d",&n,&m)){ if (!n&&!m) break; clear(); for (int i=1;i<=n;++i) for (int j=1;j<=m;++j){ ch=getchar(); while (ch!='.'&&ch!='H'&&ch!='m') ch=getchar(); if (ch=='m'){ man[++cntman].l=i; man[cntman].r=j; } if (ch=='H'){ home[++cnthome].l=i; home[cnthome].r=j; } } N=cntman+cnthome+2; for (int i=1;i<=cntman;++i) for (int j=1;j<=cnthome;++j){ dollar=abs((double)man[i].l-home[j].l)+abs((double)man[i].r-home[j].r); addedge(1+i,1+cntman+j,1,dollar); } for (int i=1;i<=cntman;++i) addedge(1,i+1,1,0); for (int i=1;i<=cnthome;++i) addedge(1+cntman+i,N,1,0); major(1,N); PRintf("%d/n",mincost); }}新闻热点
疑难解答
