Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Dfs水题……

Posted by This_poet at 2011-10-12 08:38:26 on Problem 2132
```Program poj2132;//By_Thispoet
Const
maxn=25;
Type
arr				=array[0..310]of Integer;
Var
i,j,k,m,n,p		:Longint;
map				:Array[1..maxn,1..maxn]of Longint;
v				:Array[1..maxn]of Boolean;
prime			:Array[1..2000]of Boolean;
List,num,now	:Array[0..310]of Integer;
tmp				:Array[1..2000,0..310]of Integer;
ans				:Int64;

Function Min(i,j:Longint):Longint;
begin
if i<j then exit(i);exit(j);
end;

Function Max(i,j:Longint):Longint;
begin
if i>j then exit(i);exit(j);
end;

Procedure Prime_Prepare;
begin
fillchar(prime,sizeof(prime),1);
fillchar(list,sizeof(list),0);
for i:=2 to 2000 do
if prime[i] then
begin
inc(list[0]);
list[list[0]]:=i;
m:=i*2;
while m<=2000 do
begin
prime[m]:=false;
inc(m,i);
end;
end;
fillchar(tmp,sizeof(tmp),0);
for j:=1 to 2000 do
begin
i:=j;
for k:=1 to list[0] do
begin
if (i mod list[k]=0) then
begin
p:=0;
repeat
inc(p);
i:=i div list[k];
until i mod list[k]<>0;
tmp[j,k]:=p;
end;
if i=1 then break;
end;
end;
end;

Procedure Union(now:arr);
var i:Longint;
begin
for i:=1 to list[0] do
num[i]:=Max(num[i],now[i]);
end;

Procedure Insert_Gcd(i:Longint;var now:arr);
var j,p:Longint;
begin
for j:=1 to list[0] do
if now[j]<>-1 then now[j]:=Min(now[j],tmp[i,j]) else now[j]:=tmp[i,j];
end;

Function Check(TNode:Arr):Boolean;
var i:Longint;
begin
for i:=1 to list[0] do
if TNode[i]>num[i] then exit(false);
exit(true);
end;

Procedure Dfs(i:Longint;now:arr);
var j:Longint;
Tnode:arr;
begin
if i=2 then
begin
Union(now);
exit;
end;
for j:=2 to n do
if (not v[j])and(map[i,j]>0) then
begin
TNode:=now;
Insert_Gcd(map[i,j],TNode);
if check(TNode) then continue;
v[j]:=true;
Dfs(j,TNode);
v[j]:=false;
end;
end;

BEGIN

Prime_prepare;
for i:=1 to n do for j:=1 to n do read(map[i,j]);
v[1]:=true;
fillchar(now,sizeof(now),255);
Dfs(1,now);
ans:=1;
for i:=1 to list[0] do
for j:=1 to num[i] do ans:=ans*list[i];
writeln(ans);

END.
```

Followed by: