Type: {zd0}二分匹配问题的变形,n封信要装到n个信封里,现只知道第i封信不在第j个信封,问{zh1}能确定的搭配。

Method:一封信可以有k(1~n)个信封装,即k种选择,所以可能有多种装信方案,如果在所有的装信方案中,(i0,j0)这组搭配总是存在,那么这组搭配就是确定的。

由于是“并相应地写了n个信封将信装好”,所以可以先判断是否存在一个xx匹配,如果不存在,可以确定为“none”。找出所有的xx匹配是一个NP问题,于是,

我们可以这样考虑:

任意取一个xx匹配M,对于任意的e∈M,如果e是确定的,那么删除边e后,图G就不存在xx匹配了,根据此判断所有的边是否是固定的。

key:刚开始没看准题,输入给搞错了;因为要按顺序输出,所以增加了mx[],来保存X集合的匹配。(卡在了输入输出上)

 

代码
//15ms
#include <stdio.h>
#include
<string.h>
#define NL 104

int adj[NL][NL]; // 0 is exit
int my[NL], mx[NL];
bool used[NL];
int n;

bool path(int u)
{
for (int v=1; v<=n; v++) {
if (!adj[u][v] && !used[v]) {
used[v]
= true;
if (my[v] == -1 || path(my[v])) {
my[v]
= u;
mx[u]
= v;
return true;
}
}
}
return false;
}

int main()
{
int i;
while (scanf("%d", &n) != EOF) {
int x, y;
memset(adj,
0, sizeof(adj));
while (scanf("%d%d", &x, &y)) {
if (!x && !y) break;
adj[x][y]
= 1;
}
memset(mx,
-1, sizeof(mx));
memset(my,
-1, sizeof(my));
int match = 0;
for (i=1; i<=n; i++) {
memset(used,
0, sizeof(used));
if (path(i)) match++;
}
if (match != n) {
printf(
"none\n\n");
continue;
}
int cnt = 0;
for (i=1; i<=n; i++) {
int t = mx[i];
my[t]
= -1;
adj[i][t]
= 1;
memset(used,
0, sizeof(used));
if (!path(i)) {
my[t]
= i;
cnt
++;
printf(
"%d %d\n", i, mx[i]);
}
adj[i][t]
= 0;
}
if (!cnt) puts("none");
printf(
"\n");
}
return 0;
}

 

测试数据若干:

代码
input:
3
1 2
1 3
2 1
0 0

3
1 1
2 1
3 3
0 0

2
1 1
2 2
0 0

3
1 2
1 3
2 1
2 3
0 0

5
1 2
1 4
1 5
2 1
2 3
3 2
3 5
4 1
4 3
5 2
5 4
5 5
0 0

3
1 1
2 2
3 3
0 0

1
1 1
0 0

3
1 1
2 1
3 1
0 0

output:
1 1

3 1

1 2
2 1

1 1
2 2
3 3

3 4

none

none

none