BZOJ1298[SCOI2009]骰子的学问

Description

Input

第一行为两个整数n, m。第二行有n个整数，为a1，a2, …, an。

Output

包含n行，每行m个1~n×m的正整数，各不相同，以空格分开。如果有多解，输出任意一组解；如果无解，输出一个整数0。

Sample Input & Sample Output

HINT

30%的数据满足n, m≤10

100%的数据满足3≤n, m≤200

题解：

把ai认为是i的父亲，使其连边，那么题目给出的关系构成了一个基环树森林。

对于在环外、指向环的边（即“树”的部分），使骰子的每一个面都比其父亲大。

观察1、4样例可以发现一个构造方式：对于一个大小为n环，从第一个点开始，逆着父亲边放入1~n；再从第一个点在环上的儿子开始，逆着父亲边以此放入n+1~2*n，直到放满n*m个数。

但是这个构造法在样例3中失败了。事实上，可以证明，只有在像样例3这种环大小为3，骰子面数为4的情况下，该方法会失效。对于这种情况，进行特判。

注意环大小为2或是m<=2的情况，一定无法构造。

代码：

 const
   bb:array[..]of longint=(,,,,,,,,,,,);
 var
   i,j,k,l,n,m,cnt:longint;
   fa,a,b,c:array[..]of longint;
   d:array[..,..]of longint;
 procedure ss2(x:longint);
 var i:longint;
 begin
   if a[x]< then
   begin
     for i:= to m do
     begin inc(cnt); d[x,i]:=cnt; end;
     a[x]:=;
   end;
   i:=c[x];
   while i> do
   begin
     if a[i]< then ss2(i);
     i:=b[i];
   end;
 end;
 procedure ss(x:longint);
 var i,j,k,l,xx:longint;
 begin
   a[x]:=; x:=fa[x];
   while a[x]= do
   begin
     a[x]:=; x:=fa[x];
   end;
   k:=; xx:=fa[x]; a[x]:=;
   while x<>xx do begin inc(k); a[xx]:=; xx:=fa[xx]; end;
   if k<= then begin writeln(); halt; end;
   if(k=)and(m=)then
   begin
     for i:= to  do
     begin
       d[x,+((i-)div )]:=bb[i];
       x:=fa[x];
     end;
   end else
   begin
     for i:= to m do
     begin
       l:=cnt+k;
       for j:= to k do
       begin
         d[x,i]:=l; dec(l);
         if j<>k then x:=fa[x];
       end;
       cnt:=cnt+k;
     end;
   end;
   for i:= to k do
   begin
     ss2(x); x:=fa[x];
   end;
 end;
 begin
   readln(n,m);
   for i:= to n do
   begin
     read(fa[i]);
     b[i]:=c[fa[i]]; c[fa[i]]:=i;
   end;
   for i:= to n do
   if a[i]= then ss(i);
   for i:= to n do
   begin
     for j:= to m do write(d[i,j],' ');
     writeln;
   end;
 end.