bzoj1562

很明显是二分图匹配，关键是怎么求字典序最小

想到两种做法，首先是直接匹配，然后从第一位贪心调整

第二种是从最后一个倒着匹配，每次匹配都尽量选小的，这样一定能保证字典序最小

 1 type node=record
 2        po,next:longint;
 3      end;
 4 
 5 var e:array[0..20010] of node;
 6     p,cx,cy:array[0..20010] of longint;
 7     v:array[0..20010] of boolean;
 8     i,n,len,x,y,s,d:longint;
 9 
10 procedure add(x,y:longint);
11   begin
12     inc(len);
13     e[len].po:=y;
14     e[len].next:=p[x];
15     p[x]:=len;
16   end;
17 
18 function dfs(x:longint):longint;
19   var i,y:longint;
20   begin
21     i:=p[x];
22     while i<>0 do
23     begin
24       y:=e[i].po;
25       if not v[y] then
26       begin
27         v[y]:=true;
28         if (cy[y]=0) or (dfs(cy[y])=1) then
29         begin
30           cx[x]:=y;
31           cy[y]:=x;
32           exit(1);
33         end;
34       end;
35       i:=e[i].next;
36     end;
37     exit(0);
38   end;
39 
40 begin
41   readln(n);
42   for i:=1 to n do
43   begin
44     read(d);
45     x:=i+d;
46     if x>n then x:=x-n;
47     y:=i-d;
48     if y<1 then y:=y+n;
49     if x>y then
50     begin
51       add(i,x);
52       add(i,y);
53     end
54     else begin
55       add(i,y);
56       if x<>y then add(i,x);
57     end;
58   end;
59   s:=0;
60   for i:=n downto 1 do
61     if cx[i]=0 then
62     begin
63       fillchar(v,sizeof(v),false);
64       s:=s+dfs(i);
65     end;
66   if s<n then writeln('No Answer')
67   else begin
68     for i:=1 to n do
69     begin
70       write(cx[i]-1);
71       if i<>n then write(' ');
72     end;
73   end;
74 end.

View Code