主题:小女子求助:NOIP2010奥赛初赛题目(提高组)倒数第三题的解析
越详细越好。
谢谢大家!
题目:
const
size=100;
var
n,m,x,y,i:integer;
r:array[1...size] of integer;
map:array[1..size,1..size] of boolean;
found:boolean;
function successful:boolean;
var
i:integer;
begin
fori=1 to n do
if not map[r[i][r[i mod n +1]]
then begin
successful:=false;
exit;
end;
successful:=true;
end;
procedure swap(var a,b:integer);
var
t:integer;
begin
t:=a;
a:=b;
b:=t;
end;
procedure perm(left,right:integer);
var
i:integer;
begin
if found
then exit;
if left>right
then begin
for i:=1 to n do
write(r[i],' ');
found:=true;
end;
exit;
end;
for i:=left to right do
begin
swap(r[left],r[i]);
perm(left+1,right);
swap(r[left],r[i]);
end;
end;
begin
readln(n,m);
fillchar(map,sizeof(map),false);
for i=1 to m do
begin
readln(x,y);
map[x][y]:=true;
map[y][x]:=true;
end;
for i:=1 to n do
r[i]:=i;
found:=false;
perm(1,n);
if not found
then writeln('No soloution!');
end.
输入:
9 12
1 2
2 3
3 4
4 5
5 6
6 1
1 7
2 7
3 8
4 8
5 9
6 9
输出: ?????????
谢谢大家!
题目:
const
size=100;
var
n,m,x,y,i:integer;
r:array[1...size] of integer;
map:array[1..size,1..size] of boolean;
found:boolean;
function successful:boolean;
var
i:integer;
begin
fori=1 to n do
if not map[r[i][r[i mod n +1]]
then begin
successful:=false;
exit;
end;
successful:=true;
end;
procedure swap(var a,b:integer);
var
t:integer;
begin
t:=a;
a:=b;
b:=t;
end;
procedure perm(left,right:integer);
var
i:integer;
begin
if found
then exit;
if left>right
then begin
for i:=1 to n do
write(r[i],' ');
found:=true;
end;
exit;
end;
for i:=left to right do
begin
swap(r[left],r[i]);
perm(left+1,right);
swap(r[left],r[i]);
end;
end;
begin
readln(n,m);
fillchar(map,sizeof(map),false);
for i=1 to m do
begin
readln(x,y);
map[x][y]:=true;
map[y][x]:=true;
end;
for i:=1 to n do
r[i]:=i;
found:=false;
perm(1,n);
if not found
then writeln('No soloution!');
end.
输入:
9 12
1 2
2 3
3 4
4 5
5 6
6 1
1 7
2 7
3 8
4 8
5 9
6 9
输出: ?????????