二分图最优匹配

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<unordered_map>
using namespace std;

#define IOS ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define fi first
#define se second
#define pb push_back

typedef long long ll;
typedef pair<int,int> PII;

const int N = 209;
char s[N][N];
vector<PII> house,people;
int p,h;
int a[N][N];

int lx[110], ly[110], match[110];
bool vx[110], vy[110];

int find(int x)
{
    vx[x] = 1;
    for (int i = 1; i <= h; i++)
    {
        if (!vy[i] && lx[x] + ly[i] == a[x][i])
        {
            vy[i] = 1;
            if (match[i] == -1 || find(match[i]))
            {
                match[i] = x;
                return 1;
            }
        }
    }
    return 0;
}

bool deal()
{
    memset(ly,0,sizeof ly);
    memset(lx,-0x3f,sizeof lx);
    memset(match,-1,sizeof match);
    for(int i=1; i<=p; i++)
    {
        for(int j=1; j<=h; j++)
            lx[i] = max(lx[i],a[i][j]);
    }
    for(int i=1; i<=p; i++)
    {
        while(true)
        {
            memset(vx,0,sizeof vx);
            memset(vy,0,sizeof vy);
            if(find(i)) break;
            int delta = 0x3f3f3f3f;
            for(int j=1; j<=p; j++)
            {
                if(vx[j] == 1)
                {
                    for(int k=1; k<=h; k++)
                    {
                        if(vy[k] == 0) delta = min(delta,lx[j] + ly[k] - a[j][k]);
                    }
                }
            }
            if(delta == 0x3f3f3f3f) return 0;
            for(int j = 1; j <= p; j++)
                if (vx[j] == 1) lx[j] -= delta;
            for(int k = 1; k <= h; k++)
                if (vy[k] == 1) ly[k] += delta;
        }
    }
    return 1;
}

int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m) && n)
    {
        house.clear(),people.clear();
        rep(i,1,n)
        {
            scanf("%s",s[i] + 1);
        }
        rep(i,1,n)
        {
            rep(j,1,m)
            {
                if(s[i][j] == 'm') people.pb({i,j});
                else if(s[i][j] == 'H') house.pb({i,j});
            }
        }
        p = people.size(),h = house.size();
        for(int i=0; i<p; i++)
        {
            for(int j=0; j<h; j++)
            {
                int temp = -abs(people[i].fi - house[j].fi) - abs(people[i].se - house[j].se);
                a[i+1][j+1] = temp;
            }
        }
        if(deal() == 1)
        {
            int ans = 0;
            for(int i=1; i<=h; i++)
            {
                ans += a[match[i]][i];
            }
            cout<< -ans <<"\n";
        }
    }
    return 0;
}

class HelloWorld {
    public static void main(String[] args) {
        System.out.println("Hello, World!"); 
    }
}

print('Hello world!')