题目链接：点击查看
题目大意：给出一个n*m的地图，现在有一定数量的小人要回到屋子里去，题目保证图中的小人和屋子的数量是一致的，小人回到小屋的距离是两个点坐标的曼哈顿距离，每个小屋只能容纳一个小人，现在要让所有小人都回到屋子，问怎样设计能让总的距离之和最小
题目分析：因为KM算法是在完备匹配中求最大权匹配的，但这个题目让求的是完备匹配下的最小权匹配，有一个方法可以利用KM算法，就是建立负边，这个方法之前我看zx学长做题的时候用过，将所有的边都建立负值，这样原本最小的权值在新图中就成了最大的权值，最后用KM算法求出来的最大权匹配取一个相反数就变成最小权匹配了
因为题目保证了最多只有100个小人，所以数据范围和局限性都是适合KM算法的，建完边后直接套模板就好了，还是和上个题目一样，等学会了费用流再回来更新这个题
11月22日前来更新：
时隔一个星期，终于把之前挖的坑来填上了，不多说了，直接挂代码吧，费用流的裸题了
代码：
KM：
#include<iostream>#include<cstdlib>#include<string>#include<cstring>#include<cstdio>#include<algorithm>#include<climits>#include<cmath>#include<cctype>#include<stack>#include<queue>#include<list>#include<vector>#include<set>#include<map>#include<sstream>using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=110;int la[N],lb[N];//顶标bool visa[N],visb[N];int maze[N][N];//边权int match[N];int upd[N];char s[N][N];struct Pos{int x,y;}num1[N],num2[N];int cnt1,cnt2;bool dfs(int x){visa[x]=true;for(int i=1;i<=cnt1;i++){if(!visb[i]){if(la[x]+lb[i]-maze[x][i]==0){visb[i]=true;if(!match[i]||dfs(match[i])){match[i]=x;return true;}}elseupd[i]=min(upd[i],la[x]+lb[i]-maze[x][i]);}}return false;} int KM(){memset(match,0,sizeof(match));for(int i=1;i<=cnt1;i++){la[i]=-inf;lb[i]=0;for(int j=1;j<=cnt1;j++)la[i]=max(la[i],maze[i][j]);}for(int i=1;i<=cnt1;i++){while(1){memset(visa,false,sizeof(visa));memset(visb,false,sizeof(visb));memset(upd,inf,sizeof(upd));if(dfs(i))break;int delta=inf;for(int j=1;j<=cnt1;j++)if(!visb[j])delta=min(delta,upd[j]);for(int j=1;j<=cnt1;j++){if(visa[j])la[j]-=delta;if(visb[j])lb[j]+=delta;}}}int ans=0;for(int i=1;i<=cnt1;i++)ans+=maze[match[i]][i];return ans;}int dis(const Pos& a,const Pos& b){return abs(a.x-b.x)+abs(a.y-b.y);}void init(){cnt1=cnt2=0;memset(maze,0,sizeof(maze));}int main(){// freopen("input.txt","r",stdin);//ios::sync_with_stdio(false);int n,m;while(scanf("%d%d",&n,&m)!=EOF&&n+m){init();for(int i=1;i<=n;i++)scanf("%s",s[i]+1);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(s[i][j]=='m'){num1[++cnt1].x=i;num1[cnt1].y=j;}else if(s[i][j]=='H'){num2[++cnt2].x=i;num2[cnt2].y=j;}}for(int i=1;i<=cnt1;i++)for(int j=1;j<=cnt2;j++)maze[i][j]=-dis(num1[i],num2[j]);printf("%d\n",-KM());}return 0;}
最小费用最大流：
#include<iostream>#include<cstdlib>#include<string>#include<cstring>#include<cstdio>#include<algorithm>#include<climits>#include<cmath>#include<cctype>#include<stack>#include<queue>#include<list>#include<vector>#include<set>#include<map>#include<sstream>using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=210;int n;struct Edge{int to,w,cost,next;}edge[N*N];int head[N],cnt;void addedge(int u,int v,int w,int cost){edge[cnt].to=v;edge[cnt].w=w;edge[cnt].cost=cost;edge[cnt].next=head[u];head[u]=cnt++;edge[cnt].to=u;edge[cnt].w=0;edge[cnt].cost=-cost;edge[cnt].next=head[v];head[v]=cnt++;}int d[N],incf[N],pre[N];bool vis[N];bool spfa(int s,int t){memset(d,inf,sizeof(d));memset(vis,false,sizeof(vis));queue<int>q;q.push(s);vis[s]=true;incf[s]=inf;d[s]=0;while(!q.empty()){int u=q.front();q.pop();vis[u]=false;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;int w=edge[i].w;int cost=edge[i].cost;if(!w)continue;if(d[v]>d[u]+cost){d[v]=d[u]+cost;pre[v]=i;incf[v]=min(incf[u],w);if(!vis[v]){vis[v]=true;q.push(v);}}}}return d[t]!=inf;}int update(int s,int t){int x=t;while(x!=s){int i=pre[x];edge[i].w-=incf[t];edge[i^1].w+=incf[t];x=edge[i^1].to;}return d[t]*incf[t];}char maze[N][N];struct Pos{int x,y;}num1[N],num2[N];int dis(const Pos& a,const Pos& b){return abs(a.x-b.x)+abs(a.y-b.y);}int cnt1,cnt2;void init(){memset(head,-1,sizeof(head));cnt=0;cnt1=cnt2=0;}int main(){// freopen("input.txt","r",stdin);// ios::sync_with_stdio(false);int n,m;while(scanf("%d%d",&n,&m)!=EOF&&n+m){init();for(int i=0;i<n;i++)scanf("%s",maze[i]);for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(maze[i][j]=='m'){num1[++cnt1].x=i;num1[cnt1].y=j;}else if(maze[i][j]=='H'){num2[++cnt2].x=i;num2[cnt2].y=j;}}for(int i=1;i<=cnt1;i++)for(int j=1;j<=cnt2;j++)addedge(i,j+cnt1,1,dis(num1[i],num2[j]));int s=cnt1+cnt2+1;int t=cnt1+cnt2+2;for(int i=1;i<=cnt1;i++)addedge(s,i,1,0);for(int i=1;i<=cnt2;i++)addedge(i+cnt1,t,1,0);int ans=0;while(spfa(s,t))ans+=update(s,t);printf("%d\n",ans);}return 0;}
