匈牙利算法求最大匹配（HDU-4185 Oil Skimming）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了匈牙利算法求最大匹配（HDU-4185 Oil Skimming），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2096字，纯文字阅读大概需要3分钟。

内容图文

如下图：要求最多可以凑成多少对对象

?

大佬博客：https://blog.csdn.net/cillyb/article/details/55511666

模板：

int link[maxn],vis[maxn];
bool dfs(int x)
{
    for(int i = 1; i <= num; i++)
    {
        if(!vis[i] && cp[x][i])
        {
            vis[i] = 1;
            if(link[i] == 0 || dfs(link[i]))
            {
                link[i] = x;
                return true;
            }
        }
    }
    return false;
}

int hunyary()
{
    int sum = 0;
    memset(link, 0, sizeof(link));
    for(int i = 1; i <= num; i++)
    {
        memset(vis, 0, sizeof(vis));
        if(dfs(i))
            sum++;
    }
    return sum;
}

最后的sum值就是最大的匹配值。

附练习题：HDU-4185 Oil Skimming

水平和竖直的两个‘#’，可以连成一条边，求这样的边最多有多少条。

主要是自己如何去建图：

1. 遍历数组mp对‘#’进行标号；
2. 再次遍历遇到‘#’，看他上下左右是否有‘#’，有的话在cp数组中进行连线；
3. 再利用匈牙利算法求最大匹配。

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#define FRE() freopen("in.txt","r",stdin)
#define INF 0x3f3f3f3f

using namespace std;
typedef long long ll;
const int maxn = 605;
int n,k,cnt = 0,num;
char mp[maxn][maxn];
int temp[maxn][maxn],cp[maxn][maxn];
int link[maxn],vis[maxn];

inline void init()
{
    memset(temp, 0, sizeof(temp));
    memset(cp, 0, sizeof(cp));
}

bool dfs(int x)
{
    for(int i = 1; i <= num; i++)
    {
        if(!vis[i] && cp[x][i])
        {
            vis[i] = 1;
            if(link[i] == 0 || dfs(link[i]))
            {
                link[i] = x;
                return true;
            }
        }
    }
    return false;
}

int hunyary()
{
    int sum = 0;
    memset(link, 0, sizeof(link));
    for(int i = 1; i <= num; i++)
    {
        memset(vis, 0, sizeof(vis));
        if(dfs(i))
            sum++;
    }
    return sum;
}


int main()
{
    //FRE();
    scanf("%d",&k);
    while(k--)
    {
        init();
        scanf("%d",&n);
        for(int i = 0; i < n; i++)
            scanf("%s",mp[i]);

        num = 0;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(mp[i][j] == '#')
                    temp[i][j] = ++num;
            }
        }

        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(mp[i][j] == '#')
                {
                    if(i - 1 >= 0 && mp[i-1][j] == '#') cp[temp[i][j]][temp[i-1][j]] = 1;
                    if(i + 1 < n && mp[i+1][j] == '#') cp[temp[i][j]][temp[i+1][j]] = 1;
                    if(j - 1 >= 0 && mp[i][j-1] == '#') cp[temp[i][j]][temp[i][j-1]] = 1;
                    if(j + 1 < n && mp[i][j+1] == '#') cp[temp[i][j]][temp[i][j+1]] = 1;
                }

            }
        }
        int res = hunyary();
        printf("Case %d: %d\n",++cnt, res / 2);
    }
    return 0;
}

View Code

 

内容总结

以上是互联网集市为您收集整理的匈牙利算法求最大匹配（HDU-4185 Oil Skimming）全部内容，希望文章能够帮你解决匈牙利算法求最大匹配（HDU-4185 Oil Skimming）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---