加载中…
个人资料
  • 博客等级:
  • 博客积分:
  • 博客访问:
  • 关注人气:
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

HDU 3225 搜索 匈牙利妙用

(2010-08-28 19:13:42)
标签:

hdu

3225

搜索

匈牙利

it

分类: 搜索

题目描述:

    原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=3225

    给定每个位置上不可以出现的数字,求N满足以上要求的第K(1<=K<=80)大的N(1<=N<=200)的全排列。

解题报告:

    首先可以想到用深度优先搜索(DFS)来解决这个问题,但是显然不加优化的搜索是不可能在规定时限内完成题目要求的,所以必须考虑剪枝。

    全排列可以抽象为一个二分图匹配,点集V1为1~N,点集V2也为1~N。V1(位置)和V2(花)之间可以连上边。因此可以考虑剪枝:在深度搜索到第k位的时候,判断剩下的k+1~N位可否形成一个二分图匹配,若不可以则不继续深入搜索。并且由于此过程中一直只是在维护二分图匹配,每次只需要在改动的点上做一次增广就可以了,并不需要每次都进行完整的匈牙利过程。

上文转自:http://www.cppblog.com/dango/archive/2010/08/28/124874.html

代码如下(原创):

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define N 300
int t, n, m, k, ans[N], match[N], num, match2[N];
bool vst[N][N], re[N], tmp[N];
vector<int> jeo[N];
bool find(int id, int limit)
{
    if (id <= limit) return false;
    for(int i = 0; i < jeo[id].size(); i++)
        if (!tmp[jeo[id][i]])
        {
            tmp[jeo[id][i]] = 1;
            if (match[jeo[id][i]] == -1 || find(match[jeo[id][i]], limit))
            {
                match[jeo[id][i]] = id;
                return true;
            }
        }
    return false;
}
bool solve()
{
    memset(match, -1, sizeof(int) * (n + 1));
    for(int i = 1; i <= n; i++)
    {
        memset(tmp, 0, sizeof(bool) * (n + 1));
        if (!find(i, 0)) return false;
    }
    return true;
}
bool check(int id, int tar)
{
    if(match[tar] == id) return true;
    int key = 0;
    for(int i = 1; i <= n; i++)
        if ((match2[i] = match[i]) == id) key = i;
    int t = match[tar]; match[tar] = id; match[key] = -1;
    memset(tmp, 0, sizeof(bool) * (n + 1));
    if (find(t, id)) return true;
    else for(int i = 1; i <= n; i++)
        match[i] = match2[i];
    return false;
}
bool dfs(int deep)
{
    if (deep == n + 1)
    {
        num++; if (num == k)
            return true;
        return false;
    }
    for(int i = 0; i < jeo[deep].size(); i++)
        if (!re[jeo[deep][i]] && check(deep, jeo[deep][i]))
        {
            ans[deep] = jeo[deep][i];
            re[jeo[deep][i]] = 1;
            if (dfs(deep + 1)) return true;
            re[jeo[deep][i]] = 0;
        }
    return false;
}
int main()
{
    scanf("%d", &t);
    for(int ca = 1; ca <= t; ca++)
    {
        scanf("%d%d%d", &n, &m, &k);
        for(int i = 1; i <= n; i++)
            for(int j =1; j <= n; j++) vst[i][j] = 0;
        for(int i = 0; i < m; i++)
            for(int j = 1; j <= n; j++)
            {
                int x;scanf("%d", &x);vst[j][x] = 1;
            }
        for(int i = 1; i <= n; i++)
        {
            jeo[i].clear();
            for(int j = 1; j <= n; j++)
                if (!vst[i][j]) jeo[i].push_back(j);
            sort(jeo[i].begin(), jeo[i].end());
        }
        memset(re, 0, sizeof(bool) * (n + 1)); num = 0;
        printf("Case #%d:", ca);
        if (solve() && dfs(1))
        {
            for(int i = 1; i <= n; i++) printf(" %d", ans[i]);
            putchar('\n');
        }
        else printf(" -1\n");
    }
    return 0;
}

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有