fp一个匹配问题（匈牙利算法）

来源：学生作业帮编辑：作业帮分类：综合作业时间：2024/05/23 14:02:43

fp一个匹配问题（匈牙利算法）
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,尽可能多地将信正确地装回信封.
è数据输入：
输入数据由文件名为foi.in的文本文件提供.
n文件的第一行是一个整数n（n≤100）.信和信封依次编号为1,2,…,n.
n接下来的各行中每行有2个数i和j,表示第i封信肯定不是装在第j个信封中.文件最后一行是2个0,表示结束.
结果输出:
计算结果输出到文件名为foi.out 的文本文件中.
输出文件的各行中每行有2个数i和j,表示第i封信肯定是装在第j个信封中.请按信的编号i从小到大顺序输出.若不能确定正确装入信封的任何信件,则输出“none”.
输入示例
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 4

program p1557;
var
i,j,m,n,x,y,tot,v:longint;
link:array[1..200] of longint;
cover,f:array[1..200] of boolean;
map:array[0..200,0..200] of boolean;
Function work(i:longint):boolean;
var
q,k:longint;
begin
work:=true;
for k:=1 to n do
if (map[i,k]=true) and (cover[k]=false) then
begin
q:=link[k];
link[k]:=i;
cover[k]:=true;
if (q=0) or (work(q)=true) then exit;
link[k]:=q;
end;
work:=false;
end;
Begin
assign(input,'i.i'); reset(input);
assign(output,'o.o'); rewrite(output);
readln(n);
for i:=1 to n do
for j:=1 to n do
map[i,j]:=true;
repeat
readln(x,y);
map[y,x]:=false;
until (x=0) and (y=0);
for i:=1 to n do
begin
for j:=1 to n do
cover[j]:=false;
work(i);
end;
tot:=0;
for i:=1 to n do
begin
j:=link[i];
link[i]:=0;
map[j,i]:=false;
for v:=1 to n do cover[v]:=false;
if (work(j)=false) then
begin
tot:=tot+1;
writeln(j,' ',i);
end;
map[j,i]:=true;
link[i]:=j;
end;
if tot=0 then writeln('none')
end.

线性规划主要解决经济生活中遇到的诸多问题,其中匈牙利算法适宜解决什么问题写一个算法,借助栈进行括号的匹配校验 LED驱动器匹配问题我有一个驱动器,如图,如何匹配灯珠（灯条）求一个括号算法匹配算法的代码,C语言版的数据结构栈和队列问题算法假设一个人算术表达式包含圆括弧、中括弧和花括弧三种类型的括弧,编写一个判别表达式中括弧是否正确匹配的算法检验括号匹配的算法判断题算法只能解决一个问题（理由）判断题算法只能解决一个问题（说明理由）数据结构括号匹配问题? 数据结构：括号匹配问题. 数据结构（C）请用类C语言实现括号匹配的检验这个算法完成一个 C算法,输入一算术表达式能够编程计算其中括号 “(”和“)”；“[”和“]”；“{”和“}”的匹配