信与信封问题_codevs1222_匹配

133 阅读 0 评论 88 点赞

我是靠谱客的博主认真曲奇，这篇文章主要介绍信与信封问题_codevs1222_匹配，现在分享给大家，希望可以做个参考。

题目描述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 Description

n文件的第一行是一个整数n（n≤100）。信和信封依次编号为1，2，…，n。

n接下来的各行中每行有2个数i和j，表示第i封信肯定不是装在第j个信封中。文件最后一行是2个0，表示结束。

输出描述Output Description

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

样例输入Sample Input

1 2

1 3

2 1

0 0

样例输出Sample Output

1 1

思路：

很直白的匹配问题，如果x与y肯定不在同一个信封里，那么假如一条边不可获缺,那么没有它一定无法完美匹配,由此可以推得先进行一次匹配,再对匹配的边依次删除,如果不能完美匹配就输出。

源代码/pas:

复制代码

var
  link:array[1..200]of longint;
  map:array[1..200,1..200]of boolean;
  v:array[1..200]of boolean;
  n:longint;
function find(x:longint):boolean;
var
  i,k:longint;
begin
  find:=true;
  for i:=1 to n do
  if (not v[i])and(map[x,i]) then
  begin
    k:=link[i];
    link[i]:=x;
    v[i]:=true;
    if (k=0)or find(k) then exit;
    link[i]:=k;
  end;
  find:=false;
end;
procedure main;
var
  x,y,i,ans:longint;
begin
  ans:=0;
  fillchar(link,sizeof(link),0);
  for i:=1 to n do
  begin
    fillchar(v,sizeof(v),false);
    find(i);
  end;
  for x:=1 to n do
  begin
    y:=link[x];
    link[x]:=0;
    map[y,x]:=false;
    fillchar(v,sizeof(v),false);
    if not find(y) then
    begin
      link[x]:=y;
      writeln(x,' ',y);
      ans:=1;
    end;
    map[y,x]:=true;
  end;
  if ans=0 then
  writeln('none');
end;
procedure init;
var
  i,x,y:longint;
begin
  fillchar(map,sizeof(map),true);
  readln(n);
  repeat
    readln(x,y);
    if x+y=0 then break;
    map[y,x]:=false;
  until 1<>1;
end;
begin
  init;
  main;
end.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
var
  link:array[1..200]of longint;
  map:array[1..200,1..200]of boolean;
  v:array[1..200]of boolean;
  n:longint;
function find(x:longint):boolean;
var
  i,k:longint;
begin
  find:=true;
  for i:=1 to n do
  if (not v[i])and(map[x,i]) then
  begin
    k:=link[i];
    link[i]:=x;
    v[i]:=true;
    if (k=0)or find(k) then exit;
    link[i]:=k;
  end;
  find:=false;
end;
procedure main;
var
  x,y,i,ans:longint;
begin
  ans:=0;
  fillchar(link,sizeof(link),0);
  for i:=1 to n do
  begin
    fillchar(v,sizeof(v),false);
    find(i);
  end;
  for x:=1 to n do
  begin
    y:=link[x];
    link[x]:=0;
    map[y,x]:=false;
    fillchar(v,sizeof(v),false);
    if not find(y) then
    begin
      link[x]:=y;
      writeln(x,' ',y);
      ans:=1;
    end;
    map[y,x]:=true;
  end;
  if ans=0 then
  writeln('none');
end;
procedure init;
var
  i,x,y:longint;
begin
  fillchar(map,sizeof(map),true);
  readln(n);
  repeat
    readln(x,y);
    if x+y=0 then break;
    map[y,x]:=false;
  until 1<>1;
end;
begin
  init;
  main;
end.