> 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;
> 	readln(n);
> 	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.

• Re:Dfs水题…… (914) whybert 2012-11-16 00:11:42