信与信封问题----------完美匹配

81 阅读 0 评论 54 点赞

我是靠谱客的博主清新长颈鹿，这篇文章主要介绍信与信封问题----------完美匹配，现在分享给大家，希望可以做个参考。

信与信封问题

Time Limit(Common/Java):1000MS/3000MS Memory Limit:65536KByte
Total Submit:30 Accepted:13

Description

John先生晚上写了n封信，并相应地写了n个信封将信装好，准备寄出。但是，第二天John的儿子Small John将这n封信都拿出了信封。不幸的是，Small John无法将拿出的信正确地装回信封中了。

编程任务

将Small John所提供的n封信依次编号为1,2,...,n; 且n个信封也依次编号为1,2,...,n。假定Small John能提供一组信息：第i封信肯定不是装在信封j中。请编程帮助Small John，尽可能多地将信正确地装回信封。

Input

本题有多组输入数据，你必须处理到EOF为止。
每组数据的第一行是一个整数n（n≤100）。信和信封依次编号为1,2,…,n。
接下来的各行中每行有2个数i和j，表示第i封信肯定不是装在第j个信封中。输入最后一行是2个0，表示结束。

Output

对于每组数据，输出的各行中每行有2个数i和j，表示第i封信肯定是装在第j个信封中。请按信的编号i从小到大顺序输出。若不能确定正确装入信封的任何信件，则输出“none”。
每组输出结束之后，输出一个空行。

Sample Input

3
1 2
1 3
2 1
0 0

Sample Output

1 1

#include <stdio.h> #include <string.h> #define NL 104 int adj[NL][NL]; 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"); 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) printf("none/n"); } return 0; }