POJ - 2195 Going Home 【KM】

题目链接

题意

在一张N * M 的地图上有 K 个人和 K 个房子

地图上每个点都是认为可行走的求将每个人都分配到不同的房子求他们的总的最小步数

思路

因为每个点都是可行走的我们可以直接根据坐标算出每个人都不同房子的路径然后用 KM 算法跑一下就可以了

KM算法参考

https://blog.csdn.net/thundermrbird/article/details/52231639

https://blog.csdn.net/pi9nc/article/details/12250247

AC代码

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<vector>

#include<map>

#include<set>

#include<string>

#include<list>

#include<stack>

#include <queue>

#define CLR(a, b) memset(a, (b), sizeof(a))

using namespace std;

typedef long long ll;

typedef pair <int, int> pii;

const int INF = 0x3f3f3f3f;

const int maxn = 1e2 + 5;

const int MOD = 1e9;

int nx, ny;

int linker[maxn], lx[maxn], ly[maxn];

int g[maxn][maxn];

int slack[maxn];

bool visx[maxn], visy[maxn];

bool DFS(int x)

{

    visx[x] = true;

    for (int y = 0; y < ny; y++)

    {

        if (visy[y])

            continue;

        int tmp = lx[x] + ly[y] - g[x][y];

        if (tmp == 0)

        {

            visy[y] = true;

            if (linker[y] == -1 || DFS(linker[y]))

            {

                linker[y] = x;

                return true;

            }

        }

        else if (slack[y] > tmp)

            slack[y] = tmp;

    }

    return false;

}

int KM()

{

    CLR(linker, -1);

    CLR(ly, 0);

    for (int i = 0; i < nx; i++)

    {

        lx[i] = -INF;

        for (int j = 0; j < ny; j++)

        {

            if (g[i][j] > lx[i])

                lx[i] = g[i][j];

        }

    }

    for (int x = 0; x < nx; x++)

    {

        for (int i = 0; i < ny; i++)

        {

            slack[i] = INF;

        }

        while (true)

        {

            CLR(visx, false);

            CLR(visy, false);

            if (DFS(x))

                break;

            int d = INF;

            for (int i = 0; i < ny; i++)

            {

                if (!visy[i] && d > slack[i])

                    d = slack[i];

            }

            for (int i = 0; i < nx; i++)

            {

                if (visx[i])

                    lx[i] -= d;

            }

            for (int i = 0; i < ny; i++)

            {

                if (visy[i])

                    ly[i] += d;

                else

                    slack[i] -= d;

            }

        }

    }

    int res = 0;

    for (int i = 0; i < ny; i++)

        if (linker[i] != -1)

            res += g[linker[i]][i];

    return res;

}

int dis(int x1, int y1, int x2, int y2)

{

    int x = abs(x1 - x2);

    int y = abs(y1 - y2);

    return x + y;

}

int main()

{

    int n, m;

    while (scanf("%d%d", &n, &m) && (n || m))

    {

        vector <pii> p, h;

        p.clear();

        h.clear();

        char c;

        for (int i = 0; i < n; i++)

        {

            for (int j = 0; j < m; j++)

            {

                scanf(" %c", &c);

                if (c == 'm')

                    p.push_back (pii(i, j));

                if (c == 'H')

                    h.push_back (pii(i, j));

            }

        }

        int len = p.size();

        for (int i = 0; i < len; i++)

        {

            for (int j = 0; j < len; j++)

            {

                g[i][j] = -dis(p[i].first, p[i].second, h[j].first, h[j].second);

                //printf("%d\n", g[i][j]);

            }

        }

        nx = ny = len;

        printf("%d\n", -KM());

    }

}