SHENXN's BLOG

Purdue University
Computer Science, Math

Xiaonan Shen's avatar Xiaonan Shen

[POJ2195]Going Home(KM算法)

就是一道KM的模板题,而且建图已经非常显然了。关于KM算法:

KM算法流程:

(1)初始化可行顶标值

(2)用匈牙利算法寻找完备匹配

(3)若未找到完备匹配则修改可行顶标的值

(4)重复(2)(3)直到找到相等子图的完备匹配为止
上述内容转自:二分图匹配算法总结(phoenixinter),更详细的讲述详见原文。

但是KM算法找的是最大权值,而本题要求的是最小权值。很多题解上都说把权值取反,然后最后再取反输出。但我总觉得这样做不舒服。其实也很简单,接上述文章的描述,先初始化X的可行顶标为X出发的所有边的权值的最小值,而松弛变量slack(yj) = min{w(xi, yj) - l(xi) - l(yj), |xi in S, yj not int T},每次修改顶标时,将所有在S中的l(xi)加delta,所有在T中的l(yj)减小delta。此时要记得将所有的slack值加上delta(每次初始化也可以,复杂度上没差太多)。

//POJ 2195.cpp
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>

//#define LOCAL
//#define READ_FILE
#define READ_FREAD
//#define VISUAL_STUDIO

const int MAXN = 110;
const int MAXPT = 210;

#ifdef LOCAL
#define LOCAL_TIME
//#define LOCAL_DEBUG
//#define STD_DEBUG
#endif

#ifdef LOCAL_TIME
#include<ctime>
#endif

#ifdef VISUAL_STUDIO
#pragma warning(disable: 4996)
#endif

#ifdef READ_FREAD
char fread_char;

inline void fread_init()
{
    fread_char = getchar();
}

inline int get_int()
{
    int ret = 0;
    while ((fread_char < '0') || (fread_char > '9'))
    {
        fread_char = getchar();
    }
    while ((fread_char >= '0') && (fread_char <= '9'))
    {
        ret = ret * 10 + fread_char - '0';
        fread_char = getchar();
    }
    return ret;
}

inline char get_char()
{
    char ret;
    while ((fread_char == ' ') || (fread_char == 'n'))
    {
        fread_char = getchar();
    }
    ret = fread_char;
    fread_char = getchar();
    return ret;
}
#endif

inline void read(int &a)
{
#ifdef READ_FREAD
    a = get_int();
#else
    scanf("%d", &a);
#endif
}

inline void read(char &a)
{
#ifdef READ_FREAD
    a = get_char();
#else
    scanf("%c", &a);
#endif
}

struct man_node
{
    int x, y;
};

typedef man_node house_node;

struct edge_node
{
    int to;
    int d;
    edge_node *next;
};

edge_node edge[MAXN * MAXN];
edge_node *head_edge[MAXPT];
int tot_edge;

man_node man[MAXN];
house_node house[MAXN];
int tot_man;
int tot_house;

inline void add_edge(const int u, const int v, const int d)
{
#ifdef LOCAL_DEBUG
    //printf("ADD_EDGE: M_X M_Y H_X H_Y D: %d %d %d %d %dn", man[u].x, man[u].y, house[v].x, house[v].y, d);
#endif
    edge[tot_edge].d = d;
    edge[tot_edge].to = v;
    edge[tot_edge].next = head_edge[u];
    head_edge[u] = edge + tot_edge++;
}

int n, m;
char map_pt;
int slack[MAXN], height_man[MAXN], height_house[MAXN];
int ans;
bool visit_man[MAXN], visit_house[MAXN];
int match_house[MAXN], match_d[MAXN];

inline int min(const int a, const int b)
{
    if (a == -1)
    {
        return b;
    }
    else if (b == -1)
    {
        return a;
    }
    return a < b ? a : b;
}

inline bool aug(const int u)
{
    visit_man[u] = true;
    int delta;
    for (edge_node *tmp = head_edge[u]; tmp != NULL; tmp = tmp->next)
    {
        if (!visit_house[tmp->to])
        {
            delta = tmp->d - height_man[u] - height_house[tmp->to];
            if (delta == 0)
            {
                visit_house[tmp->to] = true;
                if ((match_house[tmp->to] == -1) || (aug(match_house[tmp->to])))
                {
                    match_house[tmp->to] = u;
                    match_d[tmp->to] = tmp->d;
                    return true;
                }
            }
            else
            {
                slack[tmp->to] = min(slack[tmp->to], delta);
            }
        }
    }
    return false;
}

inline void init_km()
{
    memset(slack, -1, sizeof(slack));
    memset(height_man, -1, sizeof(height_man));
    memset(height_house, 0, sizeof(height_house));
    memset(match_house, -1, sizeof(match_house));
    memset(match_d, 0, sizeof(match_d));
    ans = 0;
    for (int i = 0; i < tot_man; i++)
    {
        for (edge_node *tmp = head_edge[i]; tmp != NULL; tmp = tmp->next)
        {
            height_man[i] = min(height_man[i], tmp->d);
        }
    }
}

inline int km()
{
    init_km();
    for (int i = 0; i < tot_man; i++)
    {
#ifdef LOCAL_DEBUG
        printf("AUG: %dn", i);
#endif
        //memset(slack, -1, sizeof(slack));
        while (1)
        {
            memset(visit_man, false, sizeof(visit_man));
            memset(visit_house, false, sizeof(visit_house));
            if (aug(i))
            {
                break;
            }
            int delta = -1;
            for (int j = 0; j < tot_house; j++)
            {
                if (!visit_house[j])
                {
                    delta = min(delta, slack[j]);
                }
            }
#ifdef LOCAL_DEBUG
            printf("DELTA: %dn", delta);
#endif
            for (int j = 0; j < tot_man; j++)
            {
                if (visit_man[j])
                {
                    height_man[j] += delta;
                }
            }
            for (int j = 0; j < tot_house; j++)
            {
                if (visit_house[j])
                {
                    height_house[j] -= delta;
                }
                else
                {
                    slack[j] += delta;
                }
            }
        }
    }
    for (int i = 0; i < tot_house; i++)
    {
#ifdef LOCAL_DEBUG
        printf("HOUSE: %d %d MAX: %d %d D: %dn", house[i].x, house[i].y, man[match_house[i]].x, man[match_house[i]].y, match_d[i]);
#endif
        ans += match_d[i];
    }
    return ans;
}

int main()
{
#ifdef LOCAL_TIME
    long long start_time_ = clock();
#endif
#ifdef READ_FILE
    freopen("2195.in", "r", stdin);
#ifndef STD_DEBUG
    freopen("2195.out", "w", stdout);
#endif
#endif
#ifdef READ_FREAD
    fread_init();
#endif
    read(n);
    read(m);
    while (n != 0)
    {
        tot_man = tot_house = 0;
        memset(head_edge, 0, sizeof(head_edge));
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                read(map_pt);
                if (map_pt == 'm')
                {
                    man[tot_man].x = i;
                    man[tot_man++].y = j;
                }
                else if (map_pt == 'H')
                {
                    house[tot_house].x = i;
                    house[tot_house++].y = j;
                }
            }
        }
        tot_edge = 0;
        for (int i = 0; i < tot_man; i++)
        {
            for (int j = 0; j < tot_house; j++)
            {
                add_edge(i, j, std::abs(man[i].x - house[j].x) + std::abs(man[i].y - house[j].y));
            }
        }
        printf("%dn", km());
        read(n);
        read(m);
    }
#ifdef LOCAL_TIME
    printf("run time: %lld msn", (clock() - start_time_) / 1000);
#endif
#ifdef READ_FILE
    fclose(stdin);
#ifndef STD_DEBUG
    fclose(stdout);
#endif
#endif
    return 0;
}

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Link to this article: https://www.shenxn.io/poj2195.html