题目描述:
原题链接: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;