首页 > 代码库 > 1562: [NOI2009]变换序列 - BZOJ
1562: [NOI2009]变换序列 - BZOJ
Description
Input
Output
Sample Input
5
1 1 2 2 1
Sample Output
1 2 4 0 3
HINT
30%的数据中N≤50;
60%的数据中N≤500;
100%的数据中N≤10000。
二分图匹配,倒着匹配,每次选小的增广(随便乱yy一下,应该就可以证明是字典序最小的吧)
1 const 2 maxn=10010; 3 var 4 first,link:array[0..maxn]of longint; 5 a:array[0..maxn,0..1]of longint; 6 next,last:array[0..maxn]of longint; 7 n:longint; 8 9 procedure swap(var x,y:longint); 10 var 11 t:longint; 12 begin 13 t:=x;x:=y;y:=t; 14 end; 15 16 procedure init; 17 var 18 i,x:longint; 19 begin 20 read(n); 21 for i:=1 to n do 22 begin 23 read(x); 24 a[i,0]:=i+x; 25 a[i,1]:=i-x; 26 if a[i,0]>n then dec(a[i,0],n); 27 if a[i,1]<1 then inc(a[i,1],n); 28 if a[i,0]>a[i,1] then swap(a[i,0],a[i,1]); 29 end; 30 end; 31 32 var 33 time:longint; 34 flag:array[0..maxn]of longint; 35 36 function path(x:longint):boolean; 37 var 38 i:longint; 39 begin 40 for i:=0 to 1 do 41 if (i=0) or (a[x,i]<>a[x,i-1]) then 42 if flag[a[x,i]]<>time then 43 begin 44 flag[a[x,i]]:=time; 45 if (link[a[x,i]]=0) or (path(link[a[x,i]])) then 46 begin 47 link[a[x,i]]:=x; 48 exit(true); 49 end; 50 end; 51 exit(false); 52 end; 53 54 procedure work; 55 var 56 i:longint; 57 begin 58 for i:=n downto 1 do 59 begin 60 inc(time); 61 if path(i)=false then 62 begin 63 writeln(‘No Answer‘); 64 exit; 65 end; 66 end; 67 for i:=1 to n do 68 if link[a[i,0]]=i then write(a[i,0]-1,‘ ‘) 69 else write(a[i,1]-1,‘ ‘); 70 end; 71 72 begin 73 init; 74 work; 75 end.
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。