题目描述：

n 个小人回到 n 间房子，要求一对一，告诉每个人的位置和每个房子的位置，问n个人移动的总距离最少是多少

题解：

最小权值匹配模板
在这里插入图片描述
我们分别记录人和房，然后人与房连边并记录边权
将所有边权值取相反数，然后跑一遍最优权值匹配模板
详细看代码，仔细看看怎么构造图

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 300 + 10;
int sx[maxn], sy[maxn], vx[maxn], vy[maxn], match[maxn];
int money[maxn][maxn], slack[maxn];
int n;
int x,y;
bool dfs(int x)
{
    vx[x] = true;
    for(int i = 1; i <= n; i++)
    {
        int xx= sx[x] + sy[i] - money[x][i];
        if(!vy[i] && !xx)
        {
            vy[i] = true;
            if(match[i]==-1 || dfs(match[i]))
            {
                match[i] = x;
                return true;
            }
        }
        else if(slack[i] > xx)
            slack[i] = xx;
    }
    return false;
}
void bestmatch()
{
    for(int i = 1; i <= n; i++)
    {
        while(1)
        {
            memset(vx, false, sizeof(vx));
            memset(vy, false, sizeof(vy));
            memset(slack, 0x3f, sizeof(slack));
            if(dfs(i))
                break;
            int dd = inf;
            for(int i = 1; i <= n; i++)
                if(!vy[i] && dd>slack[i])
                    dd = slack[i];
            for(int i = 1; i <= n; i++)
            {
                if(vx[i])
                    sx[i] -= dd;
                if(vy[i])
                    sy[i] += dd;
            }
        }
    }
}
struct node{
    int x,y;
}H[maxn],m[maxn];
int main()
{
    while(~scanf("%d%d", &x,&y))
    {
        if(x==0&&y==0)break;
        int tot1=0;
        int tot2=0;
        for(int i=1;i<=x;i++)
        {
            for(int j=1;j<=y;j++)
            {
                char x;
                cin>>x;
                if(x=='H')
                {
                    H[++tot1].x=i;
                    H[tot1].y=j;
                }
                else if(x=='m')
                {
                    m[++tot2].x=i;
                    m[tot2].y=j;
                }
                else continue;
            }
        }
        memset(sy, 0, sizeof(sy));
        for(int i=1;i<=tot1;i++)
        {
            for(int j=1;j<=tot2;j++)
            {
                money[i][j]=(abs(H[i].x-m[j].x)+abs(H[i].y-m[j].y))*(-1);
                sx[i] = max(sx[i], money[i][j]);
            }
        }
        n=tot1;
        memset(match, -1, sizeof(match));
        bestmatch();
        int sum = 0;
        for(int i = 1; i <= n; i++)
            sum += money[match[i]][i];
        printf("%d\n", sum*(-1));
    }
    return 0;
}